IMO 1998 - संयोजक

Question

मैं इस IMO Combinatorics समस्या का प्रयास कर रहा हूं $1998$ P2 जो इस प्रकार है:

एक प्रतियोगिता में, वहाँ हैं $m$ प्रतियोगियों और $n$ जज, जहां $n \geq 3$एक अजीब पूर्णांक है। प्रत्येक न्यायाधीश प्रत्येक प्रतियोगी को "पास" या "असफल" के रूप में दर देता है। मान लीजिए$k$ एक संख्या ऐसी है, जो किन्हीं दो न्यायाधीशों के लिए, उनकी रेटिंग के लिए सबसे अधिक होती है $k$प्रतियोगी। साबित करो$$\frac{k}{m}\geq \frac{n-1}{2n}$$

मैं पूरी तरह से हैरान हूं कि कैसे शुरू किया जाए, क्या आप मुझे कोई संकेत दे सकते हैं?

Answer 1

संयोजनों की संख्या पर विचार करें $(\{j_1, j_2\},c)$, कहां है $\{j_1, j_2\}$ अलग न्यायाधीशों की एक जोड़ी है, और $c$एक प्रतियोगी है जिस पर वे सहमत हैं। आप इस मात्रा में दो तरीकों से पहुंच सकते हैं:

1. प्रतियोगियों से अधिक, उन जजों की जोड़ी की संख्या जो उन पर सहमत हैं।

2. जजों की जोड़ी पर योग, उन प्रतियोगियों की संख्या जिन पर वे सहमत हैं।

फिर 1 में सम्‍मिलित होने वाली मात्रा को नीचे दिए गए भाव से जोड़ा जा सकता है $n$ (याद कीजिए $n$ विषम है), जबकि मात्रा 2 में अभिव्यक्त की जा रही है। ऊपर से घिरा हो सकता है $k$। संयोजन से वांछित असमानता पैदा होती है।