Dört renkli bir alanda dört renkli bir kesişme olduğunu kanıtlayın. $100×100$ ızgara [yinelenen]

Question

Bir $100×100$ızgara dört renk ile renklendirilmiştir. Her satır ve sütunda her renkten tam olarak 25 blok vardır. Kesişen dört bloğun hepsinin farklı renklere sahip olacağı şekilde iki sıra ve sütun arasında bir kesişim olduğunu kanıtlayın.

Bunu değişmezlik kullanarak kanıtlamaya çalışıyorum. Ama nasıl ilerleyeceğimi bilmiyorum. Bunun doğru bir yaklaşım olup olmadığını da bilmiyorum, bu yüzden herhangi bir fikir takdir ediliyor :)

Answer 1

Olduğuna dikkat edin $\binom{4}{2} \cdot 25^2$ her satırda farklı renk çiftleri olduğu için $100 \cdot \binom{4}{2} \cdot 25^2$Toplamda aynı sırada bulunan farklı renk çiftleri. Şimdi dikkat edin$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Yani, genelleştirilmiş güvercin deliği ilkesine göre, iki sütun var$>75$aynı sıradaki farklı renk çiftleri. Aynı satırda 76 çift farklı renk olduğunu varsayalım. Renklerin isimlerinin setten olduğunu söyle$\{0,1,2,3\}$. Şimdi, iddia doğru değilse, o zaman ya$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ veya $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ bunları kapsamak için kullanabileceğimiz olası çiftler $2$sütunlar (WLOG). Bir sınırımız olduğundan ilk durum açıkça imkansızdır.$25$ her renk için ve ikinci durum imkansızdır çünkü $3$ renkler toplamı kaplamak için yeterli değil $76 \cdot 2=152$bloklar. Yani iddia doğru.

Düzenleme: "Aynı satırdaki farklı renk çiftleri" ile ne demek istediğimi anlayamıyorsanız, aşağıdaki @Mike'dan gelen yorumlara bakın.