राज्य अमरीका USAMO $1989$, मुसीबत $2$

Question

मुसीबत $2$ USAMO से, $1989$: $20$ एक स्थानीय टेनिस क्लब के सदस्यों ने वास्तव में निर्धारित किया है $14$आपस में दो-व्यक्ति गेम, प्रत्येक सदस्य कम से कम एक गेम में खेलता है। सिद्ध करें कि इस अनुसूची के भीतर छह खेलों का एक सेट होना चाहिए$12$ अलग खिलाड़ी।

एक समाधान पर मेरा प्रयास: चूंकि वहाँ हैं$20$ खिलाड़ी, जिनमें से प्रत्येक ने कम से कम एक खेल खेला है, सभी खिलाड़ियों को समायोजित करने के लिए कम से कम मैचों का आयोजन किया जाना चाहिए $10$। अभी,$4$अधिक मैच छोड़ दिया जाता है, के द्वारा खेला जा सकता है जो अधिक से अधिक $8$ इनमे से $20$खिलाड़ियों। इस प्रकार, कम से कम $12$ खिलाड़ियों को इससे अधिक नहीं खेलना है $1$मैच, और इसलिए छह खेलों का एक सेट मौजूद होना चाहिए$12$अलग खिलाड़ी । यह, मेरा मानना ​​है, एक कठोर प्रमाण का मार्गदर्शक सिद्धांत होगा।

मेरे मन में निम्नलिखित शंकाएँ हैं:

1. क्या मेरा तर्क ध्वनि, किसी भी नुकसान से मुक्त है?
2. यदि सही है, तो गणितीय तर्क के सबूत में उपरोक्त तर्क को कैसे फ्रेम किया जाए?

संपादित करें: जैसा कि टिप्पणियों में बेन ने कहा है, इटैलिक में बयान अनुचित है। मैंने इस प्रमाण को बनाते हुए बहुत सारी संभावनाओं की अनदेखी की, ऐसा लगता है। इस प्रकार, मैं अधिक उचित प्रमाण के साथ आगे बढ़ने के लिए कुछ संकेत प्राप्त करना चाहूंगा।

Answer 1

मुझे डर है कि वहाँ एक गड्ढा है। यदि आप यह साबित करने की कोशिश करते हैं कि 12 अलग-अलग खिलाड़ियों के साथ 6 गेम हैं, जिन्होंने ठीक 1 गेम खेला है तो आप असफल होंगे। यहाँ एक उदाहरण है:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

जबकि 12 अलग-अलग खिलाड़ियों के साथ 6 गेम हैं, केवल 5 गेम बिल्कुल एक गेम वाले खिलाड़ियों के बीच हैं।

तो यहाँ एक संकेत है: खिलाड़ियों को दो समूहों में विभाजित करें, एक खेल के साथ और अधिक वाले। फिर एक खेल के साथ जोड़ी खिलाड़ी, एक खेल के साथ जोड़ी खिलाड़ियों के साथ एक खिलाड़ी के साथ अधिक और अंत में अधिक खेल वाले खिलाड़ियों के साथ।

संपादित करें : दूसरा तरीका

यदि प्रत्येक व्यक्ति को एक शीर्ष के रूप में और हर खेल को एक बढ़त के रूप में देखा जाता है, तो सवाल यह साबित करने के लिए कहता है कि कम से कम आकार का मेल है $6$। समान रूप से, हम यह साबित कर सकते हैं कि अधिकतम मिलान का आकार$MM$ कम से कम आकार का है $6$। ध्यान दें कि एक अधिकतम मिलान विभाजन कोने में दो सेटों में होता है, एक किनारों के साथ$MM$आकार का $2\cdot |MM|$, और एक आकार के बिना $20 - 2\cdot |MM|$हमारी समस्या के लिए। चूंकि सभी कोने कम से कम डिग्री के हैं$1$, हम निष्कर्ष निकालते हैं कि कम से कम हैं $20 - 2\cdot |MM|$दो विभाजनों के बीच किनारों। अभी,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$