सिद्ध करें कि चार रंगों में एक चार रंगीन चौराहे मौजूद हैं $100×100$ ग्रिड [डुप्लीकेट]

Question

ए $100×100$ग्रिड चार रंगों से रंगी होती है। हर पंक्ति और स्तंभ में प्रत्येक रंग के बिल्कुल 25 ब्लॉक हैं। सिद्ध करें कि दो चौराहों और स्तंभों के बीच एक चौराहा मौजूद है जैसे कि सभी चार चौराहों पर अलग-अलग रंग होते हैं।

मैं आक्रमणकारी का उपयोग करके यह साबित करने की कोशिश कर रहा हूं। लेकिन मुझे नहीं पता कि कैसे आगे बढ़ना है। मैं यह भी नहीं जानता कि क्या यह सही दृष्टिकोण है इसलिए किसी भी विचार की सराहना की जाती है :)

Answer 1

ध्यान दें कि वहाँ हैं $\binom{4}{2} \cdot 25^2$ प्रत्येक पंक्ति पर विभिन्न रंगों के जोड़े, इसलिए हैं $100 \cdot \binom{4}{2} \cdot 25^2$विभिन्न रंगों के जोड़े जो कुल में एक ही पंक्ति में हैं। अब, ध्यान दें कि$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$। तो, सामान्यीकृत कबूतर सिद्धांत द्वारा, दो स्तंभ हैं$>75$विभिन्न रंगों के जोड़े जो एक ही पंक्ति में हैं। कहते हैं कि विभिन्न रंगों के 76 जोड़े हैं जो एक ही पंक्ति में हैं। कहते हैं रंगों के नाम सेट से होते हैं$\{0,1,2,3\}$। अब, अगर दावा सच नहीं है, तो या तो$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ या $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ संभावित जोड़े हैं जिनका उपयोग हम इन्हें कवर करने के लिए कर सकते हैं $2$कॉलम (WLOG)। पहला मामला स्पष्ट रूप से असंभव है क्योंकि हमारे पास एक सीमा है$25$ प्रत्येक रंग के लिए, और दूसरा मामला तब से असंभव है $3$ रंग कुल कवर करने के लिए पर्याप्त नहीं हैं $76 \cdot 2=152$ब्लॉक। तो दावा सही है।

संपादित करें: यदि आप समझ नहीं पा रहे हैं कि "एक ही पंक्ति में अलग-अलग रंगों के जोड़े" से मेरा क्या मतलब है, तो @Mike से नीचे की टिप्पणियाँ देखें।