IMO 1990 ग्राफ थ्योरी समस्या
इसलिए मैंने IMO 1990 P2 के लिए यह समाधान देखा:
समस्या 2: मान लीजिए n≥3, और S को एक वृत्त पर 2n on 1 अलग-अलग बिंदुओं का एक सेट होने दें। मान लें कि S के k अंक काले रंग के हैं। एस के एक रंग को "अच्छा" कहा जाता है यदि काले बिंदुओं की कम से कम एक जोड़ी होती है जैसे कि जोड़ी के बीच के आर्क में से एक के आंतरिक भाग में एस के बिल्कुल n अंक होते हैं, तो कश्मीर के कम से कम मूल्य का पता लगाएं ताकि प्रत्येक रंग का हो एस "अच्छा" हो।
समाधान: एक ग्राफ जी पर विचार करें, जिसके कोने बिंदुओं का प्रतिनिधित्व करते हैं और दो कोने के बीच एक धार होती है यदि उनके द्वारा परिभाषित आर्क्स में से एक का आंतरिक भाग बिल्कुल n कोने होता है। हम यह दिखाना चाहते हैं कि जब हम कश्मीर को रंग देते हैं, तो दो आसन्न कोने रंगीन होते हैं। चूंकि प्रत्येक शीर्ष की डिग्री 2 है, इसलिए व्यायाम 4.1.4 से पता चलता है कि जी असंतुष्ट चक्रों का संघ है। ध्यान दें कि यदि हम 1 से 2n - 1 तक की संख्याओं को जोड़ते हैं, तो 1 n + 2 के निकट है और n + 2 2n + 3 के निकट है, जो कि शीर्ष 4 है। इस प्रकार 1 और 4 एक ही चक्र में हैं। यदि 2 एन - 1 3 से विभाज्य नहीं है, तो जी में केवल एक चक्र होता है, इसलिए के = एन स्पष्ट रूप से वांछित संख्या है। यदि 2n 2 1 3 से विभाज्य है, तो ग्राफ 2n। 1 3 की लंबाई के तीन अव्यवस्थित चक्रों द्वारा बनता है। इस प्रकार हम लगातार लंबवत रंग प्राप्त किए बिना एक चक्र के अधिकांश 2n 3 1 3 =1 2 = n − 2 3 शीर्ष पर रंग कर सकते हैं। इस प्रकार k = 3 · ((n - 2) / 3) + 1 = n - 1 वह संख्या है जो हम इस मामले में चाहते हैं।
मैं यह नहीं समझता कि यह क्यों कहता है कि प्रत्येक कोने में DEGREE 2 होगा, क्या कोई मुझे यह समझा सकता है?
जवाब
डिग्री अन्य शीर्षों की संख्या है जो प्रत्येक शीर्ष पर किनारों को जोड़ने वाली होती है। इस स्थिति में, सर्कल से प्रत्येक दिशा में n + 1 अंक गिनकर दो जुड़े हुए कोने पाए जाते हैं।