Buktikan bahwa ada empat persimpangan berwarna dalam empat warna $100×100$ kisi [duplikat]

Question

SEBUAH $100×100$kisi diwarnai dengan empat warna. Tepatnya ada 25 blok setiap warna di setiap baris dan kolom. Buktikan bahwa terdapat perpotongan antara dua baris dan kolom sehingga keempat blok yang berpotongan memiliki warna yang berbeda.

Saya mencoba membuktikannya dengan menggunakan invarian. Tapi saya tidak tahu bagaimana melanjutkannya. Saya juga tidak tahu apakah ini pendekatan yang benar sehingga setiap ide dihargai :)

Answer 1

Perhatikan bahwa ada $\binom{4}{2} \cdot 25^2$ pasang warna berbeda di setiap baris, jadi ada $100 \cdot \binom{4}{2} \cdot 25^2$pasang warna berbeda yang berada pada baris yang sama secara total. Sekarang, perhatikan itu$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Jadi, menurut prinsip lubang merpati umum, ada dua kolom dengan$>75$pasang warna berbeda yang berada di baris yang sama. Katakanlah ada 76 pasang warna berbeda yang berada di baris yang sama. Katakanlah nama warna tersebut berasal dari kumpulan$\{0,1,2,3\}$. Sekarang, jika klaim itu tidak benar, maka salah satunya$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ atau $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ adalah pasangan yang mungkin bisa kita gunakan untuk menutupi ini $2$kolom (WLOG). Kasus pertama jelas tidak mungkin karena kami memiliki batas$25$ untuk setiap warna, dan kasus kedua tidak mungkin sejak itu $3$ warna tidak cukup untuk menutupi total $76 \cdot 2=152$blok. Jadi klaim itu benar.

Edit: Jika Anda tidak dapat memahami apa yang saya maksud dengan "pasang warna berbeda yang berada di baris yang sama", lihat komentar di bawah dari @Mike.