असतत गणित पर इलेक्ट्रॉनिक मैनुअल। वैज्ञानिक मंच dxdy. विषम शीर्षों की संख्या की समता पर प्रमेय

हैलो, मैं इस मंच का उपयोग निम्नलिखित प्रमाण का परीक्षण करने के लिए कर रहा हूं। सामान्य तौर पर, यह समस्या है, लेकिन मैंने सुना है कि स्कूली बच्चे इसे ओलंपियाड में हल करते हैं।

एक कार्य।
देश में 100 शहर हैं, कुछ जोड़े शहर सड़कों से जुड़े हुए हैं। किन्हीं चार शहरों के बीच कम से कम दो सड़कें हैं। यह ज्ञात है कि प्रत्येक शहर से ठीक एक बार गुजरने वाला कोई मार्ग नहीं है।
सिद्ध कीजिए कि दो शहरों को इस तरह से चुनना संभव है कि शेष शहरों में से कोई भी दो चुने हुए शहरों में से कम से कम एक सड़क से जुड़ा हो।

प्रमाण।
शहर शिखर हैं। पसलियां सड़कें हैं।

पता करें कि क्या ग्राफ को डिस्कनेक्ट किया जा सकता है। यदि घटक 3 से अधिक है, तो हम एक से 2 शीर्षों का चयन करते हैं, एक दूसरे से, और तीसरे से एक और। यह पता चला है कि उन्हें अधिकतम एक किनारे से जोड़ा जा सकता है। कार्य शर्त का उल्लंघन किया जाता है।
मान लीजिए कि दो घटक हैं, जिनमें से प्रत्येक में एक से अधिक शीर्ष हैं। फिर उन्हें पूरा होना चाहिए। यदि ऐसा नहीं है, तो हम पहले से दो गैर-आसन्न शीर्ष लेते हैं, दूसरे से कोई दो। ऐसे सेट में केवल दो शहरों को जोड़ा जा सकता है। विरोधाभास। दूसरे घटक के लिए भी यही है। तो दोनों पूर्ण हैं। खैर, फिर हम पहले से कोई एक शीर्ष और दूसरे घटक में से कोई एक लेते हैं। कार्य की शर्त पूरी होती है।
मान लीजिए कि अब एक घटक 0 डिग्री का केवल एक शीर्ष है। तब पता चलता है कि दूसरा घटक 99 शीर्षों से होगा। यदि किसी भी शीर्ष से दो से अधिक किनारों को हटा दिया जाता है, तो स्थिति का तुरंत उल्लंघन किया जाता है: हम डिग्री 0 का एक शीर्ष लेते हैं, दो किनारों के बिना एक शीर्ष और शिखर जिसमें से कोई किनारा नहीं होता है (1 किनारा होगा)। इसका मतलब है कि प्रत्येक शीर्ष से केवल एक किनारे को हटाया जा सकता है। लेकिन अगर आप ऐसा करते हैं, तो प्रत्येक शीर्ष पर एक विषम डिग्री होगी (इससे पहले, प्रत्येक में 98 था)। और विषम अंशों की संख्या केवल सम संख्या हो सकती है, इसलिए या तो हम कहीं दो किनारों को हटा दें और 4 शहरों पर प्रतिबंध का उल्लंघन किया जाए, या हम सभी किनारों और फिर पूर्ण शीर्ष को छोड़ दें।

आइए उन शहरों को कॉल करें जहां से अन्य सभी शहरों q और p के लिए सड़कें हैं।

इसके बाद, हम प्रेरण द्वारा सिद्ध करते हैं कि किसी भी जुड़े ग्राफ के लिए 4 शहरों और एक r.path की बाधा के साथ, शर्त संतुष्ट होगी।
आधार। 4 शीर्षों में से स्पष्ट है: हम किसी भी फैले हुए पेड़ को लेते हैं और उसमें एक शीर्ष चुनते हैं जो एक पत्ते से अलग होता है, और दूसरा एक पत्ता होता है।

संक्रमण। मान लीजिए कि शीर्षों का एक आलेख है। फिर उस आकार से छोटे सभी रेखांकन के लिए जिसके लिए समस्या की स्थिति संतुष्ट है, सब कुछ सिद्ध हो जाता है।

हमें यह साबित करने की आवश्यकता है कि हम प्रेरण परिकल्पना का उपयोग कर सकते हैं।
आइए उस शीर्ष को कॉल करें जिसे बाहर फेंक दिया जाएगा।
यदि ऊपर से एक ग्राफ है, जहां किसी भी 4 शहरों के लिए दो सड़कें होनी चाहिए, तो यह शहरों के लिए भी सच होना चाहिए: हम सभी शहरों को एक के बिना मानेंगे। मुख्य बात यह है कि ग्राफ कनेक्टिविटी नहीं खोता है, और यह हमेशा केवल हैंगिंग वर्टेक्स, यदि कोई हो, को हटाकर किया जा सकता है।

यदि यह पता चला कि r.path में बनाया गया था, तो इसे इसके किसी एक सिरे से नहीं जोड़ा जा सकता था (अन्यथा, ग्राफ़ में r.path)। तो, हटाने के लिए, यह फैले हुए पेड़ में एक लटकता हुआ शीर्ष है। यदि यह पता चला कि यह अभी भी असंभव है: यह एक शीर्ष से अंत तक जुड़ा हुआ था जिसे हटा दिया गया था, फिर हम दूसरे को हटा देते हैं। साथ ही, यह पता नहीं चल सका कि शीर्ष एक शीर्ष के माध्यम से दोनों सिरों से जुड़ा हुआ है: यह 3 शिखरों पर एक ग्राफ होगा (और यदि अंत में दूसरा पथ है, तो एक आर है। पथ), लेकिन यह 4 से अधिक शीर्षों के ग्राफ़ के लिए सिद्ध होता है।
जाहिर सी बात है कि फैले हुए पेड़ में लटके हुए शीर्ष को हटाने से कनेक्टिविटी नहीं खोती है।

अब यह साबित हो गया है कि अगर कोई ग्राफ है, तो उसे दोगुना कर दिया जाता है। स्थिति, तो आप एक शीर्ष चुन सकते हैं, जिसे हटाने के बाद एक छोटा ग्राफ प्राप्त होगा जो प्रारंभिक स्थिति को संतुष्ट करता है। तो हम प्रेरण परिकल्पना का उपयोग कर सकते हैं।

अब , शीर्षों के ग्राफ से जुड़ा है, शहरों के इस देश का अपना p और q है। यह स्पष्ट है कि यदि p या q से कोई किनारा है, तो कुछ भी सिद्ध करने की आवश्यकता नहीं है। तो माना कि p से q तक कोई सड़क नहीं है।
जिस समुच्चय तक p से सड़कें हैं उसे A कहा जाएगा और जिस समुच्चय तक q से सड़कें हैं उसे B कहा जाएगा।
माना p से q तक कोई सड़क नहीं है। फिर शहर को सड़क मार्ग से शहर से न जोड़ने दें। लेकिन फिर उसके पास p और q दोनों के लिए सड़कें होनी चाहिए, अन्यथा हम शीर्ष , , p और q लेते हैं।
तब यह पता चलता है कि शहर को सड़कों से शहरों से नहीं जोड़ा जा सकता है
लेकिन तब आप शहर को एक नया p बना सकते हैं, और q को वही छोड़ सकते हैं (या इसके विपरीत)।

इसलिए, केवल एक मामला बचा है: p और q एक सड़क से जुड़े हुए हैं।
हम सेट के नाम वही छोड़ देते हैं।
प्रेरण परिकल्पना द्वारा: ग्राफ में हैमिल्टनियन पथ नहीं है।
एक बार फिर से अगर पूरे सेट से लेकर पूरे सेट तक सड़कें हैं तो सब कुछ पहले ही साबित हो चुका है.

अब शीर्षों का एक जोड़ा है और , जिसमें से कोई किनारा नहीं है।
यदि केवल , तो वह सब कुछ है जिसे q कवर नहीं करता है, तो p. फिर - एक नया बड़ा शहर।
खाली है तो उससे जुड़ा है और सब कुछ सिद्ध होता है।

यदि और के बीच कोई किनारा नहीं है, तो हम लेते हैं , , और p - एक किनारा होगा। सो है। अब यह पता चला है कि यह एक पूर्ण सबग्राफ है, हालांकि, साथ ही (अन्यथा, हम लेते हैं या , पी या क्यू, यदि आवश्यक हो, और असंबद्ध कोने)।
अब से शीर्षों पर एक उप-अनुच्छेद पर विचार करें। आइए सरल तरीकों से शीर्षों के पूरे सेट को कवर करने का प्रयास करें।
मान लीजिए कि कवर केवल 4 सरल पथों से बना है। आइए प्रत्येक से एक चरम शिखर लें: यदि कोई किनारा है, तो दो चरम शिखरों को जोड़ना और एक लंबा रास्ता प्राप्त करना संभव था। परिणाम चार कोने पर एक विरोधी क्लिक है। विरोधाभास।
अब हम जानते हैं कि समुच्चय अधिकतम 3 सरल पथों से ढका हुआ है। हम प्रत्येक सरल को एक शीर्ष के रूप में मानेंगे: यदि किसी भी छोर पर आना संभव है, तो इसके अंदर प्रत्येक शीर्ष के माध्यम से एक बार जाना संभव है - यह आसान है, लेकिन यह किया जा सकता है, क्योंकि प्रत्येक शीर्ष से p और q दोनों के माध्यम से पहुँचा जा सकता है। अब केवल अधिकतम 3 शीर्ष हैं।
पथ में एक या अधिक शीर्ष हो सकते हैं। यदि अधिक है, तो हम पूरे पथ को उसके एक चरम शिखर से पहचानते हैं।
आइए बाएं सेट को कॉल करें - , दायां - , मध्य - (पथ कोने में संकुचित होते हैं)।
हम शीर्ष के बारे में भूल सकते हैं: यदि यह पता चलता है कि आई-पथ है, तो पहले से ही प्रेरण परिकल्पना के साथ एक विरोधाभास होगा।
केस 1. मध्य सेट खाली है। फिर हम बस (सिर्फ कोने के साथ) बाएं सेट के चारों ओर जाते हैं, इसके अलावा किसी भी शीर्ष से शुरू करते हुए, हम अंत में , फिर p में, फिर तुरंत q, फिर अंदर जाते हैं और बस दाएं सेट के चारों ओर जाते हैं। यह एक रास्ता निकला।
स्थिति 2. मध्य समुच्चय में एक शीर्ष है। सब कुछ समान है, लेकिन p से q तक हम इस शीर्ष से गुजरते हैं।
स्थिति 3. अब मध्य समुच्चय में शीर्ष हैं

1. बोर्ड में एक क्रॉस का आकार होता है, जो वर्ग बोर्ड से कोने के वर्गों को हटाकर प्राप्त किया जाता है $4 \गुना 4$। क्या शतरंज के शूरवीर की चाल के साथ इसके चारों ओर जाना और मूल क्षेत्र में लौटना संभव है, एक बार सभी क्षेत्रों का दौरा करने के बाद?
2. डिजिट के देश में 1, 2, 3, 4, 5, 6, 7, 8, 9 नाम के 9 शहर हैं। एक यात्री को पता चलता है कि दो शहर एक एयरलाइन द्वारा जुड़े हुए हैं यदि और केवल अगर इन शहरों के नाम 3 से विभाज्य है। क्या शहर 1 से शहर 9 तक जाना संभव है?
3. स्मॉल शहर में 15 टेलीफोन हैं। क्या उन्हें तारों से जोड़ा जा सकता है ताकि प्रत्येक टेलीफोन ठीक पांच अन्य से जुड़ा हो?
4. राज्य में 100 शहर हैं, और उनमें से प्रत्येक से 4 सड़कें निकलती हैं। राज्य में कितनी सड़कें हैं?
5. कक्षा में 30 लोग हैं। क्या ऐसा हो सकता है कि उनमें से 9 के 3 मित्र हों (इस कक्षा में), 11 के 4 मित्र हों, और 10 के 5 मित्र हों?
6. स्मॉल शहर में 15 टेलीफोन हैं। क्या उन्हें तारों से जोड़ा जा सकता है ताकि 4 टेलीफोन हों, प्रत्येक तीन अन्य से जुड़े हों, 8 टेलीफोन, प्रत्येक छह से जुड़े हों, और 3 टेलीफोन, प्रत्येक पांच अन्य से जुड़े हों?
7. राजा के पास 19 जागीरदार बैरन हैं। क्या ऐसा हो सकता है कि प्रत्येक जागीरदार बैरोनी में 1, 5 या 9 पड़ोसी बैरोनी हों?
8. क्या उस राज्य में ठीक 100 सड़कें हो सकती हैं जिसमें प्रत्येक शहर से 3 सड़कें निकलती हैं?
9. जॉन, डिज़नीलैंड से पहुंचे, ने कहा कि मुग्ध झील पर 7 द्वीप हैं, जिनमें से प्रत्येक 1, 3 या 5 पुलों की ओर जाता है। क्या यह सच है कि इनमें से कम से कम एक पुल अनिवार्य रूप से झील के किनारे की ओर जाता है?
10. सिद्ध कीजिए कि पृथ्वी पर रहने वाले और विषम संख्या में हाथ मिलाने वाले लोगों की संख्या सम होती है।
11. क्या एक समतल पर 9 खंड खींचना संभव है ताकि प्रत्येक अन्य तीन को ठीक से काट सके?
12. सात के देश में 15 शहर हैं, जिनमें से प्रत्येक सड़क मार्ग से कम से कम 7 अन्य से जुड़ा हुआ है। सिद्ध कीजिए कि किसी भी शहर से दूसरे शहर में जाना संभव है (शायद दूसरे शहरों से गुजरते हुए)।
13. साबित करें कि $n$ शिखर वाला एक ग्राफ, प्रत्येक डिग्री कम से कम $(n - 1)/2$ जुड़ा हुआ है।
14. फ़ार फ़ार अवे में परिवहन का केवल एक ही साधन है - फ़्लाइंग कारपेट। राजधानी से 21 कालीन लाइनें हैं, एक डालनी शहर से और 20 अन्य सभी शहरों से। साबित करें कि राजधानी से डालनी (संभवतः स्थानान्तरण के साथ) के लिए उड़ान भरना संभव है।
15. देश के हर शहर से 100 सड़कें जाती हैं, और आप किसी भी शहर से किसी भी दूसरे तक जा सकते हैं। एक सड़क को मरम्मत के लिए बंद कर दिया गया था। सिद्ध कीजिए कि अब भी किसी भी शहर से दूसरे शहर जाना संभव है।
16. क) 120 सेमी लंबे तार का एक टुकड़ा दिया गया है। क्या तार को तोड़े बिना, 10 सेमी के किनारे वाले घन का एक फ्रेम बनाना संभव है?
    बी) आवश्यक फ्रेम बनाने के लिए तार को कम से कम कितनी बार तोड़ना होगा?
17. सिद्ध कीजिए कि जिस आलेख में किन्हीं दो शीर्षों को ठीक एक सरल पथ से जोड़ा जाता है, वह एक वृक्ष है।
18. सिद्ध कीजिए कि एक वृक्ष के किन्हीं दो शीर्षों को ठीक एक सरल पथ से जोड़ा जाता है।
19. सिद्ध कीजिए कि वृक्ष में एक शीर्ष होता है जिससे ठीक एक किनारा निकलता है (ऐसे शीर्ष को लटकता हुआ कहा जाता है)।
20. ग्राफ के सभी शीर्षों का घात 3 है। सिद्ध कीजिए कि इसका एक चक्र है।
21. सिद्ध कीजिए कि पेड़ से किसी भी किनारे को हटाने से वह डिस्कनेक्ट किए गए ग्राफ़ में बदल जाता है।
22. ट्रेलैंड देश में 101 शहर हैं, और उनमें से कुछ सड़कों से जुड़े हुए हैं। वहीं, ठीक एक रास्ता किन्हीं दो शहरों को जोड़ता है। इस देश में कितनी सड़कें हैं?
23. सिद्ध कीजिए कि एक जुड़ा हुआ ग्राफ जिसके किनारों की संख्या शीर्षों की संख्या से एक कम है, एक वृक्ष है।
24. वॉलीबॉल नेट $50 \बार 600$ वर्ग के आयत जैसा दिखता है। सबसे बड़ी संख्या में तार क्या हैं जिन्हें बिना जाल के अलग किया जा सकता है?
25. एक निश्चित देश में 30 शहर हैं, जिनमें से प्रत्येक प्रत्येक सड़क से जुड़ा हुआ है। सड़कों की सबसे बड़ी संख्या क्या है जिसे मरम्मत के लिए बंद किया जा सकता है ताकि प्रत्येक शहर से प्रत्येक तक यात्रा करना संभव हो?
26. साबित करें कि किसी भी जुड़े हुए ग्राफ में एक शीर्ष को सभी किनारों से बाहर निकालना संभव है ताकि वह जुड़ा रहे।
27. देश में 100 शहर हैं, जिनमें से कुछ एयरलाइंस से जुड़े हुए हैं। यह ज्ञात है कि आप किसी भी शहर से किसी अन्य के लिए उड़ान भर सकते हैं (संभवतः स्थानान्तरण के साथ)। साबित करें कि हर शहर का दौरा करना संभव है, जिसमें से अधिक नहीं है
    क) 198 उड़ानें;
    बी) 196 उड़ानें।
28. ओज़र्नया देश में 7 झीलें हैं, जो 10 चैनलों से जुड़ी हुई हैं, और आप किसी भी झील से तैरकर किसी भी अन्य झील में जा सकते हैं। इस देश में कितने द्वीप हैं?
29. वर्ग में 20 बिंदुओं को चिह्नित किया गया था और गैर-अंतर्विभाजक खंडों द्वारा एक दूसरे के साथ और वर्ग के शीर्षों के साथ जोड़ा गया था ताकि वर्ग त्रिभुजों में विभाजित हो जाए। आपको कितने त्रिभुज मिले?
30. एक ग्राफ जिसमें 5 शीर्ष होते हैं, जिनमें से प्रत्येक एक किनारे से किसी अन्य से जुड़ा होता है, तलीय नहीं होता है।
31. क्या तीन घर बनाना, तीन कुएँ खोदना, और हर घर से हर कुएँ तक रास्तों को जोड़ना संभव है ताकि रास्ते आपस में न टकराएँ?
32. सिद्ध कीजिए कि 10 शीर्षों वाला आलेख, प्रत्येक घात 5, तलीय नहीं है।
33. सिद्ध कीजिए कि समतलीय ग्राफ में एक शीर्ष होता है जिसकी घात 5 से अधिक नहीं होती है।
34. 11 कोने वाले एक पूर्ण ग्राफ़ का प्रत्येक किनारा दो रंगों में से एक में रंगा हुआ है: लाल या नीला। साबित करें कि या तो "लाल" या "नीला" ग्राफ समतल नहीं है।
35. हेप्टागन को उत्तल पेंटागन और हेक्सागोन में इस तरह विभाजित किया गया है कि इसका प्रत्येक कोने विभाजन के कम से कम दो बहुभुजों का एक शीर्ष है। सिद्ध कीजिए कि विभाजन में पंचभुजों की संख्या कम से कम 13 है।

2. निम्नलिखित ग्राफ ट्रैवर्सल समस्या को हल करें:

किसी देश की राजधानी और 100 अन्य शहर हैं। कुछ शहर (राजधानी सहित) एकतरफा सड़कों से जुड़े हुए हैं। प्रत्येक गैर-राजधानी शहर को छोड़कर 20 सड़कें हैं, और प्रत्येक गैर-राजधानी शहर में प्रवेश करने वाली 21 सड़कें हैं। सिद्ध करें कि किसी भी शहर से राजधानी तक पहुंचना असंभव है।

एक सड़क को राजधानी में प्रवेश करने दो। तब "आने वाली" सड़कों की कुल संख्या 21 100 + a के बराबर होती है, और "बाहर जाने वाली" सड़कों की कुल संख्या अधिकतम होती है

20 100 + (100-ए)। इसलिए, 21 100 + ए 20 100 + (100 - ए), यानी 2 ए 0।

तो ए = 0।

3.3.2.1. डिग्राफ G1 (V,E): V=(a, b, c, d, e, f), को एक बीजीय प्रणाली के रूप में परिभाषित किया गया है।

ए) कम किए गए संबंध के लिए, ज्यामितीय रूप से एक डिग्राफ को परिभाषित करें। बी) डिग्राफ के आसन्नता मैट्रिक्स का निर्माण करें।

0) आर = ((ए, बी), (बी, ए), (बी, सी), (सी, बी), (सी, ए), (ए, सी), (डी, ई), (ई, डी) );

1) आर = ((ए, बी), (बी, ए), (बी, सी), (सी, बी), (सी, डी), (डी, सी), (सी, ए), (ए, सी) );

2) आर = ((ए, बी), (बी, ए), (बी, सी), (सी, बी), (सी, डी), (डी, सी), (डी, ई), (ई, डी) );

3) आर = ((ए, बी), (बी, सी), (ए, सी), (बी, ई), (सी, एफ), (सी, डी), (डी, एफ), (एफ, ई) );

4) आर = ((बी, सी), (ए, डी), (बी, ए), (डी, सी), (बी, डी), (सी, ए), (एफ, डी), (एफ, सी) );

5) आर = ((बी, ए), (ए, ए), (बी, सी), (सी, डी), (डी, सी), (डी, बी), (डी, ए), (डी, ई) );

6) आर = ((ए, बी), (ए, सी), (ए, डी), (सी, ए), (डी, ई), (ई, डी), (सी, सी), (डी, बी) );

7) आर = ((बी, ए), (सी, सी), (ए, डी), (सी, ए), (डी, ई), (ई, सी), (डी, बी), (ई, एफ) );

8) आर = ((ए, बी), (ए, सी), (ए, डी), (ई, ए), (डी, ई), (ई, डी), (सी, बी), (डी, डी) );

9) आर = ((ए, ई), (ए, ए), (ए, डी), (सी, ए), (डी, ई), (डी, डी), (सी, सी), (बी, डी) )

3.3.2.2. डिग्राफ को ज्यामितीय रूप से दिया गया है। शीर्षों की संयोजकता निर्दिष्ट करें।

8) 1

3.3.2.3. एक डिग्राफ का आसन्नता मैट्रिक्स दिया गया है। ए) ज्यामितीय रूप से एक डिग्राफ निर्दिष्ट करें, सी) एक घटना मैट्रिक्स का निर्माण करें।

        

001100

001000

3.3.2.4। एक डिग्राफ का आपतन मैट्रिक्स दिया गया है। ए) ज्यामितीय रूप से एक डिग्राफ निर्दिष्ट करें, सी) एक आसन्न मैट्रिक्स का निर्माण करें।

3.3.2.5. निम्नलिखित ग्राफ ट्रैवर्सल समस्याओं को हल करें:

0) व्रुनलैंड से आने वाली दीमा ने कहा कि वहां कई झीलें हैं, जो नदियों से जुड़ी हुई हैं। प्रत्येक झील से तीन नदियाँ बहती हैं, और प्रत्येक झील में चार नदियाँ बहती हैं। साबित करो कि वह गलत है।

1) किसी न किसी राज्य में हर शहर हर सड़क से जुड़ा होता है। पागल राजा सड़कों पर एकतरफा यातायात शुरू करना चाहता है ताकि किसी भी शहर को छोड़कर उस पर वापस लौटना असंभव हो। क्या ऐसा करना संभव है?

2) ऐसा कहा जाता है कि पांच लोगों की एक कंपनी में प्रत्येक दो अन्य को जानता है। क्या ऐसी कंपनी संभव है?

3) एक निश्चित राज्य में 101 शहर हैं। सभी शहर एकतरफा सड़कों से जुड़े हुए हैं, प्रत्येक शहर में 50 सड़कें प्रवेश करती हैं और प्रत्येक शहर से 50 सड़कें निकलती हैं। सिद्ध कीजिए कि अधिकतम दो सड़कों पर गाड़ी चलाकर किसी भी शहर से दूसरे शहर तक जाना संभव है।

4) एक तल पर 6 बिंदु दिए गए हैं ताकि उनमें से कोई भी तीन एक ही सीधी रेखा पर न हों। डॉट्स की प्रत्येक जोड़ी एक नीली या लाल रेखा से जुड़ी होती है। सिद्ध कीजिए कि दिए गए बिंदुओं में से तीन को इस प्रकार चुनना संभव है कि उनके द्वारा बनाए गए त्रिभुज की सभी भुजाएँ एक ही रंग में रंग जाएँ।

5) एक निश्चित राज्य में 101 शहर हैं। कुछ शहर एकतरफा सड़कों से जुड़े हुए हैं, प्रत्येक शहर में 40 सड़कें प्रवेश करती हैं और 40 सड़कें प्रत्येक शहर से निकलती हैं। सिद्ध कीजिए कि तीन से अधिक सड़कें नहीं चलाकर किसी भी शहर से दूसरे शहर तक जाना संभव है।

6) क्या शहर में 10 बस मार्गों को खींचना और उन पर स्टॉप सेट करना संभव है ताकि कोई फर्क नहीं पड़ता कि 8 मार्ग क्या हैं, उनमें से किसी पर भी एक स्टॉप नहीं है, और 9 मार्ग सभी स्टॉप से ​​​​गुजरते हैं।

7) भृंग घन के किनारों पर रेंगता है। क्या यह सभी किनारों से क्रमिक रूप से गुजर सकता है, प्रत्येक किनारे पर ठीक एक बार जा रहा है? संकेत: इस प्रश्न के बारे में सोचें: एक भृंग कितनी बार प्रत्येक शीर्ष पर जा सकता है?

8) कलाकार ने "एक वर्ग की रूपरेखा और उसके विकर्ण" चित्र चित्रित किया। क्या वह कागज से पेंसिल निकाले बिना और एक ही रेखा को दो बार खींचे बिना अपना चित्र बना सकता था?संकेत: प्रत्येक बिंदु से, पेंसिल पथ के आरंभ और अंत को छोड़कर, समान संख्या में रेखाएँ निकलनी चाहिए।

9) अर्कडी, बोरिस। व्लादिमीर, ग्रिगोरी और दिमित्री ने बैठक में हाथ मिलाया (प्रत्येक ने एक-एक बार हाथ मिलाया)। कुल कितने हैंडशेक किए गए?

3.3.2.6. निम्नलिखित ग्राफ ट्रैवर्सल समस्याओं को हल करें:

0) उरीपिंस्क मेट्रो में तीन लाइनें होती हैं और इसमें कम से कम दो टर्मिनल स्टेशन और कम से कम दो ट्रांसफर हब होते हैं, और कोई भी टर्मिनल स्टेशन ट्रांसफर स्टेशन नहीं होता है। आप प्रत्येक पंक्ति से प्रत्येक में कम से कम दो स्थानों पर जा सकते हैं। ऐसे मेट्रो मानचित्र का एक उदाहरण बनाएं, यदि आप जानते हैं कि यह कागज से पेंसिल उठाए बिना और एक ही खंड को दो बार खींचे बिना किया जा सकता है।संकेत: यह मत भूलो कि रिंग लाइनें हैं।

3) बोर्ड में एक क्रॉस का आकार होता है, जिसे 4 × 4 वर्ग बोर्ड से कोने की कोशिकाओं को हटाकर प्राप्त किया जाता है। क्या शतरंज के शूरवीर की चाल के साथ इसके चारों ओर जाना और मूल क्षेत्र में लौटना संभव है, एक बार सभी क्षेत्रों का दौरा करने के बाद?

4) एक पैदल यात्री एक शहर की छह सड़कों के चारों ओर घूमता था, प्रत्येक ठीक दो बार गुजरता था, लेकिन उनके चारों ओर नहीं जा सका, प्रत्येक को केवल एक बार गुजरना पड़ा। यह हो सकता है?

5) एक भृंग 3 3 3 घन के केंद्र में बैठता है। सिद्ध कीजिए कि किनारों पर रेंगते समय वह सभी घनों 1 1 1 का एक बार चक्कर नहीं लगा पाएगा।

6) कई कोशिकाओं को 6x6 वर्ग में चिह्नित किया जाता है ताकि कोई भी चिह्नित कोशिकाओं के सामान्य पक्षों से गुजरते हुए किसी भी चिह्नित एक से किसी अन्य चिह्नित एक पर जा सके। एक चिह्नित सेल को टर्मिनल कहा जाता है यदि यह ठीक एक चिह्नित सेल की तरफ होता है। कई सेल चिह्नित करें ताकि आपको a) 10, b) 11, c) 12 सेल मिलें।

7) एक मक्खी a) एक अष्टफलक b) एक घन के किसी एक शीर्ष पर बैठती है। क्या वह ठीक एक बार उसकी सभी पसलियों पर रेंग सकती है और वापस आ सकती है

मूल शीर्ष? (नोट: एक अष्टफलक दो चतुर्भुज पिरामिड होते हैं जो आधारों पर चिपके होते हैं।)

8) कागज से पेंसिल को उठाए बिना, छह खंडों को इस तरह से कैसे बनाएं कि 4 गुणा 4 वर्ग ग्रिड के शीर्षों पर स्थित 16 बिंदुओं को पार किया जाए?

9) क्या रूबिक क्यूब की सतह पर प्रत्येक वर्ग में एक विकर्ण खींचना संभव है ताकि एक गैर-अंतर्विभाजक पथ प्राप्त हो?संकेत: रूबिक्स क्यूब की सतह पर 54 वर्ग होते हैं।

3.4. ग्राफ अनुकूलन समस्याएं

यदि निर्देशित ग्राफ G1 (V,E) का एक चाप किसी वास्तविक संख्या a (u,v) से जुड़ा है, जिसे भार कहा जाता है, तो शीर्षों का क्रम v 0, v 1,...,vp एक पथ को परिभाषित करता है। जी 1 और इसकी लंबाई के लिए

वजन के योग के रूप में परिभाषित:

यदि मनमाना

स्तंभ, प्रत्येक चाप का भार एक के बराबर होता है, तो पथ की लंबाई चापों की संख्या के बराबर होती है। सबसे छोटे रास्ते की समस्या सबसे अधिक बार हल करते समय उत्पन्न होती है

परिवहन और असतत कार्य गतिशील प्रोग्रामिंगआदि। सबसे छोटे पथ की लंबाई को r (v i,v j) द्वारा दर्शाया जाता है और इसे v i से v j तक की दूरी कहा जाता है (दूरी ऋणात्मक हो सकती है)। किसी भी डिग्राफ के लिए, कोई निर्माण कर सकता है दूरी मैट्रिक्सआर = आर (आई, जे)। मैट्रिक्स को पंक्ति से पंक्ति में भर दिया जाता है, बाईं ओर (दाएं) शीर्ष का चयन करता है। मान बाएं शीर्ष को पंक्ति के किसी एक शीर्ष से जोड़ने वाले चापों की सबसे छोटी संख्या है।

यदि v i से v j तक कोई पथ नहीं है, तो हम r (v i, v j) = सेट करते हैं। यदि हमारे ग्राफ के प्रत्येक समोच्च की लंबाई धनात्मक है, तो सबसे छोटा पथ हमेशा एक प्राथमिक पथ होगा, अर्थात। अनुक्रम v 1 ,...,v p में कोई दोहराव नहीं होगा।

ग्राफ D(vi) के केंद्र से शीर्ष vi का औसत विचलन बराबर है:

डी (vi) 1 आर (vi, वी),

एम वी वी

जहाँ m - ग्राफ़ में चापों की संख्या, v - ग्राफ़ के शीर्षों से होकर गुज़रती है, n - ग्राफ़ के शीर्षों की संख्या, i = 1..n.

जिस शीर्ष के लिए D(vi) न्यूनतम निकलता है, उसे ग्राफ का केंद्र कहा जाता है (कई कोने संभव हैं - ग्राफ का केंद्र)।

रास्ता या मार्गएक ग्राफ पर G1 (V,E) इसके शीर्षों और किनारों का एक क्रम है v1e1v2e2v3…vnen vn+1 जिसमें

कोई भी दो आसन्न तत्व आपतित हैं। पथ को सरल कहा जाता है यदि चांदी और उस पर पहले और आखिरी को छोड़कर सभी कोने अलग-अलग हों।

एक मार्ग को एक श्रृंखला कहा जाता है यदि उसके सभी किनारे अलग-अलग हों। एक मार्ग को सरल पथ कहा जाता है यदि उसके सभी शीर्ष और इसलिए किनारे अलग-अलग हों।

एक ग्राफ में एक चक्र एक पथ है जिसमें प्रारंभिक शीर्ष अंतिम शीर्ष के साथ मेल खाता है और जिसमें कम से कम एक किनारा होता है।

एक चक्र को सरल कहा जाता है यदि उसके पहले और अंतिम को छोड़कर कोई समान शीर्ष नहीं है, अर्थात। अगर कोने अलग हैं।

यदि ग्राफ में कोई चक्र नहीं है, तो इसे चक्रीय कहा जाता है।

अब हम एक पेड़ की अवधारणा को अलग तरह से परिभाषित कर सकते हैं। चक्रों के बिना जुड़े ग्राफ को ट्री कहा जाता है।

कार्यों को पूरा करने के उदाहरण

डी(2)=डी(3)=6/8=3/4;

अत: आलेख का केंद्र शीर्ष 2 और 3 है।

2. गांव एक वर्ग के रूप में 3 ब्लॉक बटा 3 ब्लॉक के रूप में बनाया गया है (ब्लॉक साइड बी के साथ वर्ग हैं, कुल 9 ब्लॉक हैं)। (वर्ग के किनारे भी सड़कें हैं)।

चावल। 6. शॉर्टकट

यह स्पष्ट है कि पेवर के मार्ग की लंबाई कम से कम 24 है, क्योंकि उसे प्रत्येक गली से कम से कम एक बार गुजरना होगा। आइए हम साबित करें कि उसे कम से कम चार गलियों से दो बार गुजरना होगा। विषम संख्या में सड़कें ठीक आठ चौराहों पर प्रतिच्छेद करती हैं।

इसलिए, किसी भी वृत्ताकार पेवर मार्ग को कम से कम 8/2 = 4 गलियों से दो बार गुजरना होगा। पेवर मार्ग की न्यूनतम लंबाई 28 है; संभावित मार्गों में से एक चित्र 6 में दिखाया गया है।

3. ग्राफ को ज्यामितीय रूप से सेट करें और समस्या को हल करें:

स्कूल के बाद यार्ड में दौड़ने के बाद, प्रत्येक छात्र ने ठीक एक दूसरे छात्र पर एक स्नोबॉल फेंका। सिद्ध कीजिए कि सभी विद्यार्थियों को तीन टीमों में विभाजित किया जा सकता है ताकि एक टीम के सदस्य एक-दूसरे पर स्नोबॉल न फेंके।

हम स्कूली बच्चों को विमान पर डॉट्स के साथ चिह्नित करते हैं और यदि एक दूसरे पर फेंकता है तो उन्हें एक तीर से जोड़ते हैं। परिणामी तस्वीर "सींग" (एक बिंदु से एक चक्र तक जाने वाले पथ) के साथ कई चक्रों की तरह दिखाई देगी। ऐसी प्रत्येक आकृति को आसानी से तीन समूहों में विभाजित किया जा सकता है: चक्र को तोड़ते हुए, हम पहले समूह में एक छात्र को असाइन करते हैं, और परिणामी पेड़ों को सम और विषम शीर्षों में विभाजित करते हैं।

आत्म-पूर्ति के लिए कार्य

3.4.1. लिखो: 1) कोई भी रास्ता जो एक श्रृंखला नहीं है; 2) श्रृंखला और सरल श्रृंखला; 3) लूप, सिंपल लूप, यदि कोई हो।

3.4.2. डिग्राफ को ज्यामितीय रूप से दिया गया है। एक दूरी मैट्रिक्स बनाएँ। डिग्राफ के केंद्र की गणना करें।

यूलर ग्राफ।

सिद्ध करें कि डोमिनोज़ के नियमों के अनुसार डोमिनोज़ का एक पूरा सेट तैयार किया जा सकता है।

"गोल नृत्य के बारे में लेम्मा"।किसी कंपनी में, प्रत्येक व्यक्ति के ठीक दो मित्र होते हैं। सिद्ध कीजिए कि यदि सभी मित्र हाथ मिला लें, तो वे एक या अधिक गोल नृत्य करते हैं।

देश में 101 से अधिक शहर हैं। राजधानी एयरलाइंस द्वारा 100 शहरों से जुड़ी हुई है, और राजधानी को छोड़कर हर शहर ठीक दस शहरों से जुड़ा है (एयरलाइन दोनों दिशाओं में चलती है)। यह ज्ञात है कि आप किसी भी शहर से किसी अन्य (शायद स्थानान्तरण के साथ) प्राप्त कर सकते हैं। साबित करें कि राजधानी से आने वाली आधी एयरलाइनों को बंद करना संभव है, ताकि किसी भी शहर से किसी भी शहर में जाने का अवसर बना रहे।

सिद्ध कीजिए कि 2n विषम शीर्षों वाला एक जुड़ा हुआ ग्राफ पेंसिल को कागज से ठीक n-1 बार और बिना किसी किनारे को दो बार खींचकर खींचा जा सकता है।

देश में प्रत्येक शहर से 3 रेलवे प्रस्थान कर रहे हैं। दो कंपनियां उन सभी का निजीकरण करना चाहती हैं। एंटीमोनोपॉली कमेटी की आवश्यकता है कि दोनों कंपनियों की सड़कें प्रत्येक शहर से बाहर निकलें। साबित करें कि कंपनियां आपस में सहमत हो सकती हैं ताकि एंटीमोनोपॉली कमेटी की आवश्यकता पूरी हो सके।

k किनारों के साथ जुड़ा हुआ ग्राफ G दिया गया है। साबित करें कि किनारों को सभी नंबर 1, 2, ..., k के साथ गिनना संभव है ताकि कम से कम दो डिग्री के प्रत्येक शीर्ष के लिए, इस शीर्ष से किनारों को लेबल करने वाले संख्याओं के सेट में 1 के बराबर जीसीडी हो।

विभिन्न शहरों की 20 टीमों के बीच आयोजित एक फुटबॉल टूर्नामेंट में, प्रत्येक टीम ने घर पर एक मैच खेला और दो से अधिक मैच नहीं खेले। साबित करें कि खेलों के कार्यक्रम की व्यवस्था करना संभव था ताकि प्रत्येक टीम प्रति दिन एक से अधिक खेल न खेले और पूरा टूर्नामेंट तीन दिनों में आयोजित किया जाएगा।

हैमिल्टन ग्राफ।

घन की सतह पर एक बंद आठ-खंड पॉलीलाइन खींची जाती है, जिसके कोने घन के सभी शीर्षों के साथ मेल खाते हैं। इस पॉलीलाइन के लिंक की सबसे छोटी संख्या क्या है जो घन के किनारों से मेल खा सकती है?

एक घन आठ छोटे घनों से मिलकर बना होता है। क्या यह संभव है कि बड़े घन के केंद्र को छोड़कर छोटे घनों के किनारों के साथ घूमते हुए, छोटे घनों के सभी शीर्षों के चारों ओर घूमें, प्रत्येक को ठीक एक बार देखें?

दिया गया बोर्ड 55। क्या शूरवीर सभी कक्षों के चारों ओर घूम सकता है, प्रत्येक को एक बार जाकर अपनी मूल स्थिति में लौट सकता है?

क्या एक लंगड़ा राजा (राजा तिरछे नहीं चल सकता) बिसात के सभी कक्षों के चारों ओर चल सकता है, निचले बाएँ कोने से शुरू होकर ऊपरी दाएँ कोने में समाप्त होता है?

क्या शूरवीर 8 चालें चल सकता है और शतरंज की बिसात के सभी क्षैतिज और ऊर्ध्वाधर का दौरा करके अपने मूल वर्ग में वापस आ सकता है?

लेकिन)। शतरंज की बिसात की दो कोशिकाओं पर काले और सफेद चिप्स रखे जाते हैं। उन्हें बारी-बारी से स्थानांतरित करने की अनुमति है, प्रत्येक चाल अगली चिप को किसी भी मुक्त आसन्न क्षेत्र में लंबवत या क्षैतिज रूप से स्थानांतरित करती है। क्या इन दो टुकड़ों की सभी संभावित स्थिति एक बार इस तरह की चाल के परिणामस्वरूप बोर्ड पर मिल सकती है? बी)। और अगर इसे किसी भी क्रम में चिप्स को स्थानांतरित करने की अनुमति है (जरूरी नहीं कि बदले में)?

निम्नलिखित तीन तथ्यों में से कौन सा सबसे "मजबूत" है?

किसी राज्य में, हर 2 शहर सड़क से जुड़े हुए हैं। प्रत्येक सड़क पर केवल एक दिशा की अनुमति है। साबित करें कि एक ऐसा शहर है जहां से पूरे राज्य की यात्रा करना संभव है, प्रत्येक शहर का ठीक 1 बार दौरा किया है।

किसी न किसी देश में हर शहर हर वन-वे रोड से जुड़ा होता है। सिद्ध कीजिए कि एक ऐसा शहर है जहाँ से आप किसी दूसरे तक जा सकते हैं।

एक निश्चित राज्य में 100 शहर होते हैं, और हर एक एकतरफा सड़क से जुड़ा होता है। साबित करें कि एक सड़क पर आवाजाही की दिशा बदलना संभव है ताकि किसी भी शहर से दूसरे शहर में जाना संभव हो।

सबसे "मजबूत" तथ्य और इससे दोनों उपपत्ति सिद्ध करें।

एक दौर के शतरंज टूर्नामेंट में, प्रत्येक प्रतिभागी ने प्रत्येक के साथ एक गेम खेला। साबित करें कि प्रतिभागियों को इस तरह से गिना जा सकता है कि कोई भी सीधे अगले नंबर वाले खिलाड़ी से न हारे।

देश में N शहर हैं। उनमें से किन्हीं दो के बीच या तो सड़क या रेल बिछाई जाती है। एक पर्यटक देश के चारों ओर यात्रा करना चाहता है, प्रत्येक शहर का एक बार दौरा करके, और उस शहर में लौटना चाहता है जहां से उसने अपनी यात्रा शुरू की थी। सिद्ध कीजिए कि पर्यटक उस शहर को चुन सकता है जहाँ से वह अपनी यात्रा शुरू करेगा और मार्ग इस प्रकार से चुनें कि उसे एक ही बार में परिवहन का साधन बदलना पड़े। (ऑल-रूसी ओलंपियाड, 2003)

36 शून्य और इकाई का एक क्रम 5 शून्य से शुरू होता है। लगातार पांच संख्याओं में से, सभी 32 संभावित संयोजन हैं। अनुक्रम के अंतिम पाँच अंक ज्ञात कीजिए।

"राजा आर्थर के दरबार में शूरवीर" - डिराक का प्रमेय।किंग आर्थर की गोल मेज पर 2n शूरवीर हैं, जिनमें से प्रत्येक के पास दूसरों के बीच (n-1) से अधिक दुश्मन नहीं हैं। सिद्ध कीजिए कि राजा का सलाहकार मर्लिन शूरवीरों को इस प्रकार बैठा सकता है कि शत्रु एक दूसरे के बगल में न बैठें। डिराक के प्रमेय को सामान्य रूप में निरूपित करें।

2n लोग सम्मेलन में आए, जिनमें से प्रत्येक कम से कम n अन्य लोगों को जानता है। साबित करें कि प्रतिभागियों को डबल रूम में इस तरह से रखा जा सकता है कि जो लोग एक-दूसरे को जानते हैं वे प्रत्येक कमरे में रहते हैं।

आपको कई रंगों के n चिप्स दिए गए हैं, और प्रत्येक रंग के n/2 चिप्स से अधिक नहीं हैं। सिद्ध कीजिए कि उन्हें एक वृत्त पर इस प्रकार व्यवस्थित किया जा सकता है कि एक ही रंग के दो टुकड़े अगल-बगल न खड़े हों।

दो गणराज्यों के संघीय राज्य में, प्रत्येक दो शहर एकतरफा सड़क से जुड़े हुए हैं; वहीं, सड़कों के किनारे चलते हुए आप किसी भी शहर से दूसरे शहर जा सकते हैं। ट्रैवल एजेंसी "हैमिल्टन" ऑफर एनपहले गणतंत्र के शहरों के आसपास के विभिन्न पर्यटन मार्ग और एम- दूसरे के शहरों द्वारा (इनमें से किसी भी मार्ग में गणतंत्र के प्रत्येक शहर का एक बार दौरा करना और मूल शहर में लौटना शामिल है, और यह सब गणतंत्र को छोड़े बिना)। साबित करें कि हैमिल्टन एजेंसी कम से कम पेशकश नहीं कर सकती है एम.एन.पूरे महासंघ के शहरों के माध्यम से समान पर्यटन मार्ग।

टूर्नामेंट पूर्ण ग्राफ हैं।

कक्षा में 28 छात्र हैं। शिक्षक छात्रों को स्थानांतरित कर सकता है, लेकिन प्रत्येक छात्र स्कूल के दिनों में एक ही छात्र के साथ बैठता है। प्रत्येक विद्यार्थी कम से कम कितने दिनों तक एक दूसरे के साथ बैठ सकेगा?

1000 वास्तविक संख्याओं का योग 0 है। सिद्ध कीजिए कि इन संख्याओं के कम से कम 999 जोड़ो में योग ऋणात्मक नहीं है।

एक ढेर में 25 पत्थर होते हैं। इसे दो भागों में विभाजित किया जाता है, फिर भागों में से एक को फिर से दो, आदि में विभाजित किया जाता है, जब तक कि 25 अलग-अलग पड़े हुए पत्थर प्राप्त न हो जाएं। हर बार एक ढेर को दो भागों में विभाजित किया जाता है, इन भागों में पत्थरों की संख्या का गुणनफल बोर्ड पर लिखा जाता है। सिद्ध कीजिए कि अंत में बोर्ड पर सभी संख्याओं का योग 300 होगा।

स्कूल में 1996 के बच्चे पढ़ रहे हैं। उनमें से प्रत्येक को बिल्कुल पसंद है कशेष 1995 छात्रों में से। किन मूल्यों पर कक्या यह तर्क दिया जा सकता है कि इस स्कूल के दो छात्र ऐसे होंगे जो या तो दोनों एक दूसरे को पसंद करते हैं या दोनों एक दूसरे को पसंद नहीं करते हैं?

खगोलशास्त्री 50 तारों का अवलोकन करता है, जिसके बीच की जोड़ीदार दूरियों का योग S के बराबर है। एक बादल ऊपर आया और 25 तारों को ढक लिया। सिद्ध कीजिए कि दृश्यमान तारों के बीच जोड़ीवार दूरियों का योग S/2 से कम होता है।

25 शहरों वाले देश में, तीन एयरलाइंस चाहती हैं कि शहरों के किसी भी जोड़े के लिए, इन शहरों के बीच सभी नॉन-स्टॉप उड़ानें केवल एक एयरलाइन द्वारा संचालित की जाती हैं, लेकिन कोई भी एयरलाइन यात्रियों को किसी भी शहर से किसी अन्य शहर में स्टॉप के साथ पहुंचा सकती है। एक से अधिक मध्यवर्ती शहर नहीं। साबित करें कि यह किया जा सकता है।

आयोग में 49 लोग होते हैं। प्रत्येक बैठक में आयोग के ठीक तीन सदस्य भाग लेते हैं। क्या आयोग के कार्य को इस प्रकार निर्धारित करना संभव है कि आयोग के किन्हीं दो सदस्यों की बैठक में ठीक एक बार बैठक हो?

न्यूनतम कनेक्टिविटी।

एन शहर में, किसी भी मेट्रो स्टेशन से आप किसी अन्य (संभवतः स्थानान्तरण के साथ) जा सकते हैं। सिद्ध कीजिए कि मेट्रो स्टेशनों में से एक को बिना यात्रा करने के अधिकार के मरम्मत के लिए बंद किया जा सकता है ताकि कोई भी शेष स्टेशनों में से किसी भी अन्य स्टेशन से जा सके।

साबित करें कि किसी भी जुड़े हुए ग्राफ में एक शीर्ष को सभी किनारों से बाहर निकालना संभव है ताकि वह जुड़ा रहे।

कई लोगों के समूह में, कुछ लोग एक दूसरे को जानते हैं और कुछ नहीं। हर शाम उनमें से एक अपने सभी दोस्तों के लिए रात के खाने की व्यवस्था करता है और उन्हें एक दूसरे से मिलवाता है। प्रत्येक व्यक्ति द्वारा कम से कम एक रात के खाने की व्यवस्था करने के बाद, यह पता चला कि कुछ दो लोग अभी भी एक दूसरे को नहीं जानते थे। साबित करें कि अगले डिनर में वे भी नहीं मिल पाएंगे।

एक निश्चित देश में 30 शहर हैं, और प्रत्येक शहर प्रत्येक सड़क से जुड़ा हुआ है। सड़कों की अधिकतम संख्या क्या है जिन्हें मरम्मत के लिए बंद किया जा सकता है ताकि कोई प्रत्येक शहर से प्रत्येक तक यात्रा कर सके, संभवतः दूसरे शहरों से गुजरते हुए?

ग्यारह भुजाओं वाले त्रिभुज का एक मॉडल तार से बना होता है, जिसके एक शीर्ष से सभी विकर्ण खींचे जाते हैं। दोनों बारी-बारी से एक-एक तार खाते हैं। विजेता वह है जिसके बाद मॉडल पहले दो भागों में विभाजित हो जाता है। सही ढंग से खेले जाने पर कौन जीतता है: वह जो पहले चलता है, या उसका साथी?

प्रारंभ में, बोर्ड 1n के प्रत्येक क्षेत्र पर एक चेकर होता है। किसी भी चेकर को आसन्न सेल में ले जाने के लिए पहली चाल की अनुमति है (दोनों में से एक, यदि चेकर किनारे पर नहीं है), ताकि दो चेकर्स का एक कॉलम बन जाए। फिर, अगली चाल के साथ, प्रत्येक कॉलम को किसी भी दिशा में उतने कक्षों द्वारा स्थानांतरित किया जा सकता है, जितने में चेकर्स हैं (बोर्ड के भीतर); यदि कॉलम किसी गैर-रिक्त सेल से टकराता है, तो उसे वहां खड़े कॉलम के ऊपर रखा जाता है और उसके साथ विलय कर दिया जाता है। सिद्ध कीजिए कि n-1 चालों में सभी चेकर्स को एक वर्ग पर एकत्रित करना संभव है।

1001 ग्राम, 1002 ग्राम, ..., 1101 ग्राम वजन वाले डिब्बाबंद भोजन के 101 डिब्बे हैं। वजन वाले लेबल खो गए हैं, लेकिन आपूर्ति प्रबंधक को ऐसा लगता है कि उन्हें याद है कि किसका वजन कितना हो सकता है। वह इसे कम से कम तोलों में सत्यापित करना चाहता है। दो पैन स्केल हैं: एक सटीक है, दूसरा मोटा है। एक वजन में दो डिब्बे की तुलना की जा सकती है। सटीक तराजू हमेशा दिखाते हैं कि कौन सा जार भारी है, और मोटा तराजू - केवल अगर अंतर 1 ग्राम से अधिक है (अन्यथा वे संतुलन दिखाते हैं)। आपूर्ति प्रबंधक केवल एक पैमाने का उपयोग कर सकता है। उसे कौन सा चुनना चाहिए? (ए शापोवालोव)

वॉलीबॉल नेट में 50600 कोशिकाओं के आकार के साथ एक आयत का आकार होता है। एकल रस्सियों (गांठों के बीच) की सबसे बड़ी संख्या क्या है जिसे काटा जा सकता है ताकि जाल टुकड़ों में न टूटे?

कोशिकाओं 1x1 में विभाजित एक वर्ग 8x8 के रूप में एक रस्सी ग्रिड है। सबसे लंबी रस्सी कौन सी है जिसे आप काट सकते हैं? (किसी भी छोर को दूसरे के कनेक्शन को तोड़े बिना गांठों से काटा जा सकता है, लेकिन आप एक गाँठ नहीं काट सकते ताकि कोई छोर न बने)।

नोटबुक शीट को कक्षों द्वारा 23 रंगों में चित्रित किया गया था। रंगों की एक जोड़ी को अच्छा कहा जाता है यदि इन रंगों से भरे हुए पक्ष में दो पड़ोसी कोशिकाएं हों। अच्छे जोड़े की न्यूनतम संख्या क्या है?

आइए एक भूलभुलैया को एक 8x8 शतरंज की बिसात कहते हैं, जहां कुछ क्षेत्रों के बीच विभाजन डाले जाते हैं। यदि किश्ती विभाजनों पर कूदे बिना सभी चौकों के चारों ओर घूम सकता है, तो भूलभुलैया को अच्छा कहा जाता है, अन्यथा इसे बुरा कहा जाता है। कौन सी लेबिरिंथ अधिक हैं - अच्छी या बुरी?

देश में 100 शहर हैं, जिनमें से कुछ एयरलाइंस से जुड़े हुए हैं। यह ज्ञात है कि आप किसी भी शहर से किसी अन्य के लिए उड़ान भर सकते हैं (संभवतः स्थानान्तरण के साथ)। सिद्ध कीजिए कि अधिक से अधिक निम्न कार्य करके प्रत्येक शहर का भ्रमण करना संभव है: a)। 198 उड़ानें; बी)। 196 उड़ानें।

एक शतरंज की बिसात पर, शुरू में खाली, प्यादों को निम्नलिखित नियमों के अनुसार रखा जाता है: किसी भी चार खाली कोशिकाओं का चयन किया जाता है, जिनमें से केंद्र एक आयत के कोने होते हैं, जो बोर्ड के किनारों के समानांतर होते हैं, जिसके बाद एक मोहरा रखा जाता है इन कोशिकाओं में से एक। फिर इसी तरह की चार खाली कोशिकाओं का चयन किया जाता है, उनमें से एक पर फिर से एक मोहरा रखा जाता है, और इसी तरह। इन नियमों का पालन करते हुए बोर्ड पर रखे जा सकने वाले प्यादों की सबसे बड़ी संख्या क्या है?

परिचारिका ने मेहमानों के लिए केक बेक किया। मेज पर या तो p या q लोग हो सकते हैं। टुकड़ों की न्यूनतम संख्या (जरूरी नहीं कि बराबर हो) क्या है कि केक पहले से काटा जाना चाहिए ताकि किसी भी मामले में इसे मेहमानों के बीच समान रूप से वितरित किया जा सके यदि: ए)। p और q सहअभाज्य हैं; बी)। p और q में सबसे बड़ा उभयनिष्ठ भाजक d है?

गुप्त वस्तु योजना में एक 8x8 वर्ग है, जो गलियारों द्वारा 1x1 वर्गों में विभाजित है। ऐसे वर्ग के प्रत्येक शीर्ष पर एक स्विच होता है। स्विच पर क्लिक करने से इस शीर्ष से निकलने वाले सभी मीटर-लंबे गलियारों पर तुरंत काम हो जाता है, जिससे उनकी रोशनी विपरीत दिशा में बदल जाती है। चौकीदार पूरी तरह से जली हुई वस्तु के कोने में है। वह केवल रोशनी वाले गलियारों में चल सकता है और कई बार फ्लिप स्विच कर सकता है। क्या पहरेदार के लिए यह संभव है कि वह बिना स्विच को पलटे किसी भी स्विच से दूसरे स्विच में जा सके?

एक जुड़े हुए ग्राफ में 2 एन शीर्ष, और वे सभी घात 3 के हैं। सिद्ध कीजिए कि चुनना संभव है एन+1 किनारे, ताकि चयनित किनारों का सही 3-रंग रंग विशिष्ट रूप से ग्राफ़ के सभी किनारों के सही 3-रंग के रंग को निर्दिष्ट करे (रंग सही है यदि एक सामान्य शीर्ष वाले दो किनारों के अलग-अलग रंग हैं)।

द्विदलीय ग्राफ।

सिद्ध कीजिए कि एक ग्राफ द्विदलीय होता है यदि और केवल यदि उसके सभी चक्र सम हों।

सिद्ध कीजिए कि एक वृक्ष (बिना चक्र का जुड़ा ग्राफ) एक द्विदलीय ग्राफ है।

लोगों के एक निश्चित समूह में, हर किसी का एक दुश्मन और एक दोस्त होता है। साबित करें कि इन लोगों को दो कंपनियों में विभाजित किया जा सकता है ताकि प्रत्येक कंपनी का न तो दुश्मन हो और न ही दोस्त।

रूसी फुटबॉल चैम्पियनशिप में 16 टीमें खेलती हैं। पहले राउंड में सभी टीमों ने एक-एक गेम खेला। दूसरे राउंड में सभी टीमों ने एक खेल भी खेला। सिद्ध कीजिए कि 8 टीमों के नाम इस प्रकार रखना संभव है कि उनमें से कोई भी दो एक-दूसरे से न खेले।

कुछ परिमित सेट M नोड्स को चेकर पेपर की शीट पर चिह्नित किया गया है। क्या सेट एम के कुछ बिंदुओं को सफेद और बाकी को लाल रंग में रंगना हमेशा संभव है, ताकि प्रत्येक ग्रिड लाइन पर सफेद और लाल नोड्स की संख्या के बीच का अंतर पूर्ण मूल्य में 1 से अधिक न हो? (आईएमओ, 1986)

विमान पर 1997 अंक दिए गए हैं। दो लोग बारी-बारी से इन बिंदुओं को खंडों से जोड़ते हैं, और एक खंड को दो बार नहीं खींचा जा सकता है। हारने वाला वह है जिसके बाद पहली बार विषम संख्या में लिंक के साथ एक बंद टूटी हुई रेखा बनती है। सही खेल से कौन जीतता है?

सर्कल पर 10 अंक लिए गए। इन बिंदुओं पर सिरों वाले खंडों की सबसे बड़ी संख्या क्या है जिसे खींचा जा सकता है ताकि इनमें से कोई भी तीन खंड इन बिंदुओं पर शीर्षों वाला त्रिभुज न बनाएं?

मार्टीशकिनो गांव में, हर लड़का उन सभी लड़कियों को जानता है जिन्हें वह जानता है। उसके परिचितों में हर लड़की के पास लड़कियों से ज्यादा लड़के होते हैं। साबित करें कि मार्टीशकिनो में लड़कियों से कम लड़के नहीं हैं।

हाइड्रा सिर और गर्दन से बने होते हैं (कोई भी गर्दन दो सिरों को जोड़ती है)। तलवार का एक वार हाइड्रा के किसी सिर A से निकलने वाली सभी गर्दनों को काट सकता है। लेकिन साथ ही, ए के सिर से एक गर्दन तुरंत उन सभी सिरों में बढ़ जाती है जिनसे ए जुड़ा नहीं है। हरक्यूलिस हाइड्रा को हरा देता है यदि वह इसे दो भागों में काटने का प्रबंधन करता है जो उनकी गर्दन से जुड़े नहीं हैं। सबसे छोटा N ऐसे खोजें कि हरक्यूलिस किसी भी 100-गर्दन वाले हाइड्रा को अधिक से अधिक N वार से हरा सके। (रोसऑल, 2002)

2n+1 लोगों की कंपनी में, किसी भी n लोगों के लिए, एक अलग व्यक्ति होता है जो उनमें से प्रत्येक से परिचित होता है। साबित करें कि इस कंपनी में एक व्यक्ति है जो सभी को जानता है। (रोसऑल, 2002)

फ्लैट ग्राफ।

एक तल पर 5 बिंदु होते हैं, जिनमें से कोई भी तीन एक ही सीधी रेखा पर नहीं होते हैं। सिद्ध कीजिए कि उनमें से कुछ चार एक उत्तल चतुर्भुज के शीर्षों पर स्थित हैं।

समतल पर 5 वृत्त हैं, जिनमें से प्रत्येक दो प्रतिच्छेद करते हैं। सिद्ध कीजिए कि उनमें से कुछ तीन में एक उभयनिष्ठ बिंदु है।

समतल पर 6 बिंदु हैं (प्रत्येक में 3 नीला और 3 लाल), जिनमें से कोई भी तीन एक ही सीधी रेखा पर नहीं हैं। सिद्ध कीजिए कि कुछ 2 नीले और 2 लाल बिंदु उत्तल चतुर्भुज के शीर्षों पर स्थित हैं।

चेकर्ड फ़ील्ड पर डोमिनोज़ का एक पूरा सेट होता है (प्रत्येक डोमिनोज़ 2 कोशिकाओं पर कब्जा करता है)। चलो कॉल करो क्षेत्रवर्गों का एक समूह जिसमें डोमिनोज़ की संख्या समान होती है। चलो क्षेत्र को बुलाओ मेल जोल, अगर इसके किसी भी वर्ग से एक लंगड़ा किश्ती किसी अन्य को मार सकता है। जुड़े क्षेत्रों की सबसे बड़ी संख्या क्या है जो मैदान पर हो सकती है?

आंशिक आदेश।

कक्षा में 12 लड़कियां और 12 लड़के हैं, सभी की लंबाई अलग-अलग है। शारीरिक शिक्षा पाठ में, उन्हें दो पंक्तियों (एक के पीछे एक) में बनाया गया था: लड़के - बाएं से दाएं की ऊंचाई में, और लड़कियां - दाएं से बाएं की ऊंचाई में। फिर, लड़का-लड़की के प्रत्येक जोड़े में से एक उच्च को बुलाया गया। सिद्ध करें कि आपने बारह उच्चतम छात्रों को बुलाया है।

कई अलग-अलग प्राकृतिक संख्याएँ दी गई हैं। यह ज्ञात है कि उनमें से किन्हीं तीन में से दो को चुनना संभव है ताकि एक दूसरे से विभाज्य हो। सिद्ध कीजिए कि सभी संख्याओं को दो रंगों से रंगा जा सकता है ताकि एक ही रंग की किन्हीं दो संख्याओं के लिए एक दूसरे से विभाज्य हो।

सिद्ध कीजिए कि 17 विभिन्न प्राकृत संख्याओं में से या तो 5 संख्याएँ a, b, c, d, e ऐसी हैं कि अंतिम को छोड़कर इस पाँच की प्रत्येक संख्या इसके पीछे की संख्या से विभाज्य है, या पाँच हैं संख्याएँ ऐसी हैं कि उनमें से कोई भी दूसरे से विभाज्य नहीं है।

संख्या 1, 2, 3, ..., 101 को किसी क्रम में एक पंक्ति में व्यवस्थित किया गया है। सिद्ध कीजिए कि इस श्रृंखला में से 90 संख्याओं को पार करना हमेशा संभव होता है ताकि शेष 11 आरोही या अवरोही क्रम में हों।

एल्गोरिदम।

सिद्ध कीजिए कि फैले हुए वृक्ष के शीर्षों को कंपित किया जा सकता है।

लोगों के समूह में, सभी का एक परिचित होता है। सिद्ध कीजिए कि इस समूह को दो भागों में विभाजित किया जा सकता है ताकि प्रत्येक व्यक्ति का दूसरे समूह से कोई परिचित हो।

गांव में कुछ घर तारों से जुड़े हुए हैं। पड़ोसी दो लोग हैं जिनके घर तारों से जुड़े हुए हैं। क्या हर घर में एक व्यक्ति - झूठा या शूरवीर - में बसना हमेशा संभव होगा ताकि हर कोई इस सवाल का जवाब दे: "क्या आपके पड़ोसियों में झूठे हैं?" - सकारात्मक उत्तर दिया। (हर कोई अपने पड़ोसियों के बारे में जानता है कि वह झूठा है या नहीं)।

सिद्ध कीजिए कि एक बहुफलक के शीर्षों पर प्राकृत संख्याओं को इस प्रकार व्यवस्थित किया जा सकता है कि एक किनारे से जुड़े प्रत्येक दो शीर्षों पर ऐसी संख्याएँ हों जो सहअभाज्य नहीं हैं, लेकिन प्रत्येक दो शीर्षों पर जो एक किनारे से नहीं जुड़े हैं, वे सहअभाज्य हैं।

में बंदरगाह Aventura 16 गुप्त एजेंटों को छोड़ दिया गया। उनमें से प्रत्येक अपने कुछ सहयोगियों पर नजर रखता है। यह ज्ञात है कि यदि कोई एजेंट लेकिनएजेंट का पालन करना में, फिर एजेंट मेंएजेंट का पालन नहीं करता लेकिन. किसी भी 10 एजेंटों को इस तरह से पुन: क्रमांकित किया जा सकता है कि पहला दूसरे का अनुसरण करता है, दूसरा - तीसरा, ..., दसवां - पहला। सिद्ध कीजिए कि कुछ 11 अभिकर्ताओं को इसी प्रकार से क्रमांकित किया जा सकता है।

किस पर एनआप सभी किनारों को रंग सकते हैं एन-कोयला प्रिज्म (आधार - एन-गॉन) तीन रंगों में ताकि प्रत्येक शीर्ष पर तीनों रंगों के किनारों का अभिसरण हो और प्रत्येक चेहरे (आधारों सहित) में तीनों रंगों के किनारे हों?

लेकिन)। सिद्ध कीजिए कि 3n-गोनल प्रिज्म के शीर्षों को तीन रंगों से रंगा जा सकता है ताकि प्रत्येक शीर्ष तीनों रंगों के शीर्षों से किनारों से जुड़ा हो। बी)। सिद्ध कीजिए कि यदि किसी n-गोनल प्रिज्म के शीर्षों को तीन रंगों से इस प्रकार रंगा जा सकता है कि प्रत्येक शीर्ष तीनों रंगों के शीर्षों से किनारों से जुड़ा हो, तो n 3 से विभाज्य है।

"एंटीग्राफ"।

2n+1 लोगों की कंपनी में, किसी भी n लोगों के लिए, एक अलग व्यक्ति होता है जो उनमें से प्रत्येक से परिचित होता है। साबित करें कि इस कंपनी में एक व्यक्ति है जो सभी को जानता है।

ग्राफ और बहुपद।

एक प्राकृतिक संख्या दी गई है क और बहुपद आर(एक्स) और एस(एक्स) पूर्णांक गुणांक के साथ। यह ज्ञात है कि किसी भी पूर्णांक के लिए एक्ससंख्या आर(एस(एक्स)) – एक्सद्वारा विभाजित क. साबित करें कि संख्या एस(आर(एक्स)) – एक्समें भी विभाजित है ककिसी भी पूरे के लिए एक्स.

क्या ऐसे चार बहुपद हैं जिनमें से किन्हीं तीन के योग में कम से कम एक मूल हो और किन्हीं दो के योग का कोई मूल न हो?

चक्र।

फ्लावर सिटी में 2,000 शॉर्टियां हैं। हर छोटू हर दिन अपने हर दोस्त को एक तोहफा देता है। बर्बादी से बचने के लिए, उपहार को आगे देने की अनुमति है, लेकिन उसे नहीं जिसने आपको यह उपहार दिया है। ज़्नायका ने गणना की कि शुक्रवार को उसे दिए गए उपहारों में से कोई भी उसे अगले शुक्रवार से पहले वापस नहीं किया जा सकता है। सिद्ध कीजिए कि कुछ छोटू के 13 से अधिक मित्र नहीं हैं। (ई. चेरेपोनोव)

राज्य में 100 शहर हैं। शहरों के कुछ जोड़े सड़कों से जुड़े हुए हैं, और कम से कम चार चक्रीय मार्ग हैं। सिद्ध कीजिए कि एक चक्रीय मार्ग अधिकतम 51 शहरों से होकर गुजरता है।

देश में 100 शहर हैं, कुछ जोड़े शहर सड़कों से जुड़े हुए हैं, और कुल मिलाकर 200 सड़कें हैं। यह पता चला कि किसी भी चक्रीय मार्ग की लंबाई कम से कम पांच होती है। सिद्ध कीजिए कि दो अप्रतिच्छेदी चक्रीय मार्ग हैं।

मॉस्को विश्वविद्यालय की इमारत में बहुत सारे लिफ्ट हैं, और प्रत्येक लिफ्ट यात्रियों को केवल दो मंजिलों के बीच ले जाती है (लेकिन प्रत्येक मंजिल पर आप किसी भी लिफ्ट पर जा सकते हैं जो उस पर रुकती है)। यह ज्ञात है कि लिफ्टों की एक सम संख्या का उपयोग करके, और बिना किसी मंजिल से दो बार गुजरे किसी भी मंजिल से किसी भी मंजिल तक जाना संभव है। साबित करें कि, यदि वांछित है, तो एक विषम संख्या में लिफ्ट का उपयोग करके भी ऐसा ही किया जा सकता है।

ओज़ में कई महल हैं, जिनमें से प्रत्येक में तीन रास्ते हैं। भटकते हुए शूरवीर ने अपने पुश्तैनी महल को छोड़ दिया और देश भर की यात्रा पर निकल पड़े। शूरवीर विविधता से प्यार करता है, इसलिए जब वह अगले महल में पहुंचता है, तो वह हर बार बाएं मुड़ता है यदि वह पिछली बार दाएं मुड़ता है, और यदि वह पहले बाएं मुड़ता है तो वह दाएं मुड़ता है। (रास्ते में पहले महल को पार करते हुए, शूरवीर किसी भी दिशा में मुड़ सकता है)। सिद्ध करो कि एक दिन शूरवीर अपने महल में लौट आएगा।

1 से 9 तक की संख्याओं का एक अनंत क्रम एक अंतहीन टेप पर छपा हुआ है। सिद्ध करें कि या तो संख्याओं के कुछ संयोजन को लगातार 10 बार दोहराया जाता है, या 10 सौ अंकों की संख्याओं को अवरोही क्रम में काटा जा सकता है।

विषम शीर्षों की संख्या की समानता पर प्रमेय।

एक उत्तल बहुफलक के शीर्ष, जिसके सभी फलक त्रिभुज हैं, तीन रंगों में रंगे हुए हैं। सिद्ध कीजिए कि उन तीनों चेहरों की संख्या जिनके अलग-अलग रंग हैं, सम है।

पसलियों की संख्या।

चेकर्ड पेपर के एक सफेद टुकड़े पर 12 x 12 वर्ग बनाएं। दो कोशिकाओं को आसन्न माना जाता है यदि उनके पास एक सामान्य पक्ष है। साशा एक समय में एक सेल पर पेंट करती है, प्रत्येक छायांकित सेल में अपने पड़ोसियों की संख्या को पहले से चित्रित करती है। जब सभी सेलों को भर दिया जाएगा तो सभी संख्याओं का योग क्या होगा? (ए शापोवालोव)

वर्ग 77 को छोड़कर, चेकर पेपर की एक अंतहीन शीट रंगीन। इस वर्ग में, वास्या ने एक सेल को ठीक एक आसन्न (साइड पर) सेल रंग के साथ चित्रित किया, फिर एक अन्य सेल, जिसमें अब ठीक एक आसन्न सेल रंग है, और इसी तरह। वास्या इस तरह से सबसे बड़ी संख्या में कौन सी कोशिकाएँ रंग सकती हैं?

किस पर एन>1 ऐसा हो सकता है कि किसी कंपनी में एन+1 लड़कियों और एनलड़कों, सभी लड़कियों को लड़कों की एक अलग संख्या पता है, और सभी लड़के लड़कियों की एक ही संख्या जानते हैं?

मिश्रण।

किसी बैठक में भाग लिया एन मानव। यह ज्ञात है कि उनमें से प्रत्येक दो परिचितों का कोई परस्पर परिचित नहीं है, और प्रत्येक दो व्यक्ति जो एक-दूसरे को नहीं जानते हैं, उनके ठीक दो परस्पर परिचित हैं। लेकिन)। सिद्ध कीजिए कि उपस्थित सभी लोगों के परिचितों की संख्या समान है। बी)। किस पर एनसंभावित कार्य स्थिति?

"विविधता" का शहर 10,000 निवासियों का घर है, जिनमें से हर दो या तो दुश्मनी में हैं या एक दूसरे के दोस्त हैं। हर दिन, शहर के एक से अधिक निवासी "नया जीवन शुरू नहीं कर सकते", अर्थात। अपके सब मित्रों से झगड़ना, और अपके सब शत्रुओं से मित्रता करना; जबकि कोई भी तीन निवासी आपस में मित्रता कर सकते हैं। यह साबित करने के लिए कि बिना किसी अपवाद के सभी निवासी एक-दूसरे से दोस्ती कर सकते हैं। इसके लिए निश्चित रूप से कम से कम कितने दिन पर्याप्त होंगे?

कऔर एन 1 से बड़ी प्राकृत संख्याएँ हैं। के समूह में के.एन.प्रत्येक व्यक्ति इससे अधिक परिचित है ( क–1)एनशेष में से। साबित करें कि आप चुन सकते हैं क+1 व्यक्ति ताकि वे सभी एक दूसरे को जान सकें। ( पोलिश ओलंपियाड, 68)

विमान पर 100 अंक अंकित हैं। दो लोग खेलते हैं, बारी-बारी से खेलते हैं। एक चाल में, आप दो बिंदुओं को एक तीर से जोड़ सकते हैं यदि वे पहले नहीं जुड़े हैं। उसी समय, एक तीर खींचना मना है, जिसके प्रकट होने के बाद किसी भी बिंदु से तीर के साथ किसी अन्य तक जाना संभव होगा। जो नियमों का उल्लंघन किए बिना अगला कदम नहीं उठा सकता वह हार जाता है। सही खेल से कौन जीतता है: वह जो पहले चलता है, या उसका साथी? ( हां। रोस्तोव)

वन-साइड काउंटी में, कुछ (लेकिन दुर्भाग्य से अभी तक सभी नहीं) घरों के बीच एकतरफा सड़कें हैं। उसी समय, जब कोई नई सड़क (एकतरफा यातायात के साथ) उन सम्पदाओं के बीच दिखाई देती है जो पहले सड़क से नहीं जुड़ी थीं, तो यह पता चलता है कि कोई भी नियमों का उल्लंघन किए बिना किसी भी संपत्ति से किसी भी संपत्ति तक जा सकता है। सिद्ध कीजिए कि ऐसी संभावना पहले से मौजूद है। ( हां। रोस्तोव; सेंट पीटर्सबर्ग, शहर 2000)

कुछ दोस्त मिले। उनमें से प्रत्येक ने फेडोट बुर्चेव को छोड़कर सभी के साथ हाथ मिलाया, जो कि अजीब होने के कारण, कुछ के साथ हाथ मिलाते थे, दूसरों के साथ नहीं। कुल 197 हैंडशेक हुए। फेडोट ने कितने हैंडशेक किए? ( है। रुबानोव)

देश में 100 शहर हैं, प्रत्येक शहर से कम से कम एक सड़क निकलती है। साबित करें कि कई सड़कों को बंद करना संभव है ताकि कम से कम एक सड़क प्रत्येक शहर को छोड़ दे और कम से कम एक सड़क कम से कम 67 शहरों को छोड़ दे। ( ई.ए. गिरीश, एस.वी. इवानोव, डी.वी. कार्पोव)

स्कूल में 40 क्लासरूम हैं, जो 5 अलग-अलग तरह की चाबियों से खुलते हैं और अलग-अलग तरह की चाबियों की संख्या अलग-अलग होती है. सभी 40 चाबियों को कमरों में बंद कर दिया गया था, ताकि प्रत्येक कमरे में एक चाबी बंद हो, जिसका उपयोग इस कमरे को खोलने के लिए नहीं किया जा सकता है। चौकीदार सर्गेव के पास एक कमरे की डुप्लीकेट चाबी है। साबित करें कि वह सभी कमरे खोल सकता है। ( )

स्कूल में 40 क्लासरूम हैं जो 4 अलग-अलग तरह की चाबियों से खुलते हैं। सभी 40 चाबियों को कमरों में बंद कर दिया गया था ताकि प्रत्येक कमरे में एक चाबी बंद हो, जिसका उपयोग इस कमरे को खोलने के लिए नहीं किया जा सकता है। चौकीदार सर्गेव जानता है कि चाबी कहाँ है। साबित करें कि चौकीदार सर्गेव दो अलमारियाँ की चाबियों की नकल कर सकता है, जिसका उपयोग सभी कमरों को खोलने के लिए किया जा सकता है। ( आर.ए. इस्माइलोव, एस.एल. बर्लोव, डी.वी. कार्पोव)

(एस. बर्लोव, सेंट पीटर्सबर्ग, शहर, 2001, 6-1कैट शो में, 19 बिल्लियाँ और 10 बिल्लियाँ एक पंक्ति में बैठी थीं, और प्रत्येक बिल्ली के बगल में एक बिल्ली थी जो उससे मोटी थी। सिद्ध कीजिए कि प्रत्येक बिल्ली के बगल में एक बिल्ली थी जो उससे पतली थी।

(एस. बर्लोवी) वर्गाकार मुख्य भूमि उत्तल बहुभुजों के रूप में 19 देशों में विभाजित है, और ऐसा कोई बिंदु नहीं है जिस पर चार या अधिक देशों की सीमाएँ अभिसरित हों। एक बिंदु पर अभिसरण करने वाली किन्हीं तीन सीमाओं में से एक बंद है, और दो यातायात के लिए खुली हैं। सिद्ध करें कि इन सभी देशों की यात्रा करना असंभव है, प्रत्येक में एक बार जाकर मूल देश में लौटना।

फुलकर्सोनिया देश में, कुछ शहर एयरलाइंस द्वारा जुड़े हुए हैं, और शहर ए से शहर बी तक दस से कम स्थानान्तरण के साथ जाना असंभव है। सिद्ध कीजिए कि सभी एयरलाइनों को 11 एयरलाइनों को इस प्रकार बेचा जा सकता है कि A से B तक का कोई भी मार्ग सभी 11 एयरलाइनों के स्वामित्व वाली लाइनों का उपयोग करेगा। (लोकगीत, 100)

कक्षा में प्रत्येक छात्र दो मंडलियों में है, और प्रत्येक तीन छात्रों के लिए एक मंडल है जिसमें वे एक साथ जाते हैं। सिद्ध कीजिए कि एक वृत्त है जिसमें सभी विद्यार्थी भाग लेते हैं। (डाल्एफओ ओलंपिक 2001, 104)

. दस लोग गाली-गलौज में दर्शन करने आए। उन्होंने एक समय में एक को छोड़ दिया, और प्रत्येक ने एक मनमाना जोड़ी गैलोश डाल दी, जिसमें वह फिट हो सकता था (अर्थात, अपने से छोटा नहीं)। गैलोश नहीं पहनने वाले लोगों की सबसे बड़ी संख्या क्या है?

पेरा-टेरा के शानदार देश में, अन्य निवासियों के बीच, करबास और बरबास रहते हैं। प्रत्येक करबा छह करबास और नौ बरबास से परिचित है। प्रत्येक बरबास दस करबा और सात बरबास से परिचित है। इस देश में कौन ज्यादा है - करबास या बरबस?

100 लोगों के समूह में, किन्हीं तीन में से एक ऐसा व्यक्ति होता है जो अन्य दोनों से परिचित होता है। सिद्ध करें कि इस समूह से 50 लोगों की एक कंपनी चुनना संभव है जिसमें सभी एक दूसरे को जानते हों। (एस. बर्लोव)

20 सज्जन क्लब में आए, कुछ टोपी के साथ, कुछ बिना। फिर समय-समय पर एक सज्जन ने अपनी टोपी उतार दी और दूसरे सज्जन के सिर पर रख दी, जिसके पास उस समय टोपी नहीं थी। एक घंटे बाद, 10 सज्जनों ने कहा: "मैंने अपनी टोपी जितनी बार प्राप्त की, उससे अधिक बार मैंने उसे दे दिया!" कितने सज्जन टोपी पहनकर क्लब में आए? ( एसएलबी, यू.एम. लाइफशिट्स; एसपीबी-02)

कुछ कंपनी में 10 से अधिक लोग हैं, और उनमें से प्रत्येक के पास कई परिचित हैं जो 10 से विभाज्य हैं। साबित करें कि समान संख्या में परिचितों वाले कम से कम 11 लोग हैं। ( मोल्दोवा पर आधारित SLB)

ओलंपियाड में, 8 (6) कार्य प्रस्तावित किए गए थे। प्रत्येक प्रतिभागी ने उनमें से ठीक 3 को हल किया, और किसी भी दो प्रतिभागियों ने एक से अधिक सामान्य समस्या का समाधान नहीं किया। ओलंपियाड में प्रतिभागियों की सबसे बड़ी संख्या क्या है? ( बाल्टिक वे, 01)

से एक कंपनी के लिए एनव्यक्ति, निम्नलिखित शर्त पूरी होती है: यदि कुछ 2 लोगों के समान परिचित हैं, तो प्रत्येक अन्य उनमें से एक को ठीक से जानता है। किस पर एनक्या यह संभव है? ( बाल्टिक वे, 2000)

पार्टी में 19 मेहमान आए थे। इनमें से किन्हीं 3 में 2 परिचित हैं। सिद्ध करें कि मेहमानों को 5 समूहों में विभाजित किया जा सकता है, जिनमें से प्रत्येक में हर कोई जोड़ीदार परिचित है। ( वी.एल. डोलनिकोव, एसएलबी, एसवीआई)

(लोक-साहित्य) देश में कई शहर और कई एकतरफा सड़कें हैं। प्रत्येक सड़क दो शहरों को जोड़ती है और दूसरे से नहीं गुजरती है। साथ ही, आप चाहे जो भी दो शहर ले लें, उनमें से कम से कम आप यातायात नियमों का उल्लंघन किए बिना उनमें से एक से दूसरे तक ड्राइव कर सकते हैं। साबित करें कि एक शहर है जहां से आप यातायात नियमों का उल्लंघन किए बिना किसी अन्य शहर में जा सकते हैं।

11 लोगों में से, किन्हीं दो का ठीक एक समान परिचित है। सिद्ध कीजिए कि उनमें से कम से कम एक अन्य सभी से परिचित है।

(लापोको) 5 लोगों में से किन्हीं दो का ठीक एक समान मित्र है। सिद्ध कीजिए कि उनमें से कम से कम एक अन्य सभी से परिचित है।

(पंचायतक्लासिक तथ्यों पर आधारित) देश में 120 शहर हैं। शहरों के कुछ जोड़े सड़कों से जुड़े हुए हैं जो अन्य शहरों से नहीं गुजरते हैं। प्रत्येक शहर से कम से कम तीन सड़कें निकलती हैं। सिद्ध करें कि एक गैर-स्व-प्रतिच्छेदन चक्रीय मार्ग मौजूद है जिसमें अधिकतम 11 शहर शामिल हैं।

(यू.एम. लाइफशिट्ज़) जुरलैंड देश में, कुछ शहर सड़कों से जुड़े हुए हैं (अन्य शहरों से नहीं गुजर रहे हैं), और आप किसी भी शहर से किसी अन्य तक जा सकते हैं। एक दुर्भाग्यपूर्ण दिन, एक दुष्ट उपचिक जनजाति ने एक निश्चित शहर पर कब्जा कर लिया। हर अगले दिन, सबचिकी ने या तो पकड़े गए लोगों में से एक से सटे शहर पर कब्जा कर लिया, या कब्जे वाले शहर को मुक्त कर दिया, सभी पड़ोसी लोगों को पकड़ लिया गया। वहीं, किसी भी शहर पर एक से अधिक बार कब्जा नहीं किया गया। साबित करें कि यदि उपचिक अब कुछ भी कब्जा नहीं कर सकते हैं, तो किन्हीं दो पड़ोसी शहरों में से कम से कम एक पर कब्जा कर लिया गया है।

(यू.एम. लाइफशिट्ज़भोज में जूरी के 14 सदस्यों ने भाग लिया, जिन्होंने 17 बोतल नींबू पानी पिया। जूरी के सदस्यों ने नींबू पानी की प्रत्येक बोतल को चार में पिया। साबित करें कि दो जूरी सदस्य हैं जिन्होंने एक ही बोतल से नींबू पानी नहीं पिया।

(लोक-साहित्य) टीम के 7 सदस्यों में से प्रत्येक के दो से अधिक करीबी दोस्त नहीं हैं। एक बार एक ही कमरे में, दो करीबी दोस्त लगातार चैट करना शुरू करते हैं, और इस कमरे में सभी काम बंद हो जाते हैं। साबित करें कि पूरी टीम के सुचारू संचालन को सुनिश्चित करने के लिए कप्तान के लिए तीन कमरे पर्याप्त हैं।

(यू.एम. लाइफशिट्ज़) शतरंज के 10 खिलाड़ियों ने एक दौर का टूर्नामेंट खेला, प्रत्येक ने 3 गेम जीते, हारे और ड्रॉ किए। यह ज्ञात है कि शतरंज के तीन खिलाड़ी नहीं हैं जिन्होंने आपस में मैचों में ठीक 1 अंक बनाए। सिद्ध कीजिए कि शतरंज के सभी दस खिलाड़ियों को एक गोले में इस प्रकार रखा जा सकता है कि उनमें से प्रत्येक अपने दाहिने खड़े व्यक्ति को हरा दे। शतरंज एक जीत के लिए 1 अंक, ड्रॉ के लिए 0.5 अंक और हार के लिए 0 अंक के लायक है।

(यू.एम. लाइफशिट्ज़) 10 शतरंज खिलाड़ियों ने एक दौर का टूर्नामेंट खेला, प्रत्येक ने 4 गेम जीते और हारे और एक गेम ड्रॉ किया। सिद्ध कीजिए कि शतरंज के तीन खिलाड़ियों को चुनना और उन्हें एक वृत्त में व्यवस्थित करना संभव है ताकि उनमें से प्रत्येक अपने दाहिनी ओर खड़े व्यक्ति को हरा सके।

ऑक्टोपस बारिश के सागर में रहते हैं, प्रत्येक एक या दो दोस्तों के साथ। जब सूरज निकला, तो वे सभी ऑक्टोपस जिनके दो दोस्त थे, नीले हो गए और वे सभी जिनके एक दोस्त थे, लाल हो गए। यह पता चला कि कोई भी दो दोस्त बहुरंगी हैं। फिर 10 नीले ऑक्टोपस लाल रंग में रंगे, और साथ ही 12 लाल ऑक्टोपस नीले रंग में रंगे, जिसके बाद कोई भी दो दोस्त एक ही रंग के हो गए। वर्षा के सागर में कितने ऑक्टोपस हैं?

प्रांगण में 12 स्तंभ हैं। इलेक्ट्रीशियन पेत्रोव को खंभों को तारों से इस तरह जोड़ने का काम दिया गया था कि प्रत्येक तार ठीक दो खंभों से जुड़ा हो, कोई भी दो खंबे दो बार नहीं जुड़े हों, और सबसे महत्वपूर्ण बात यह है कि किन्हीं चार खंभों के बीच ठीक तीन तार खिंचे हुए हों। ये डंडे। साबित करें कि इलेक्ट्रीशियन पेट्रोव इस कार्य का सामना नहीं कर पाएंगे।

24 लोगों में से प्रत्येक अन्य लोगों में से कम से कम 11 को जानता है। क्या उन्हें होटल के डबल कमरों में रखना हमेशा संभव है ताकि हर कोई अपने परिचित के साथ रह सके?

थोर ग्रह का आकार डोनट के आकार का है। इसमें 5 शहर हैं। क्या इन शहरों के प्रत्येक जोड़े को सड़कों से जोड़ना संभव है ताकि सड़कें कहीं भी न कटें?

न्यू बेबीलोनिया द्वीप पर 45 भाषाएँ बोली जाती हैं, और प्रत्येक निवासी उनमें से कम से कम पाँच भाषाएँ जानता है। यह ज्ञात है कि कोई भी दो निवासी एक दूसरे के साथ बातचीत कर सकते हैं, संभवतः कई अनुवादकों की मध्यस्थता के साथ। सिद्ध करें कि तब कोई भी दो द्वीपवासी 15 से अधिक दुभाषियों का उपयोग करके एक दूसरे से बात कर सकते हैं।

100 लोगों के समूह में, उनमें से कुछ एक दूसरे को जानते हैं, और समूह का प्रत्येक सदस्य कम से कम 20 अन्य को जानता है। सिद्ध कीजिए कि समूह के 40 सदस्यों को चुनना और उन्हें 20 जोड़ों में विभाजित करना संभव है ताकि प्रत्येक जोड़े में लोग परिचित हों।

पर के.एन.कार्ड में दोनों तरफ 1 से 1 तक की संख्या होती है। एन 2 प्रत्येक कएक बार प्रत्येक। सिद्ध कीजिए कि इन पत्तों को मेज पर इस प्रकार रखा जा सकता है कि प्रत्येक अंक ठीक ऊपर लिखा हो। कएक बार।

देश में 201 शहर हैं, प्रत्येक में ठीक 10 सड़कें हैं, और आप किसी भी शहर से किसी भी दूसरे तक जा सकते हैं। साबित करें कि 20 शहरों को चुनना संभव है, जिनमें से कोई भी दो सड़क से जुड़ा नहीं है।

यार्ड में कई पोल हैं, कुछ जोड़े तारों से जुड़े हुए हैं। कुल फैला हुआ एम.एन.तार, और इन तारों को चित्रित किया गया है एनरंग, और एक ही रंग के तार किसी भी पोल से नहीं निकलते। सिद्ध कीजिए कि इन तारों को फिर से रंगना संभव है ताकि सभी रंगों के तारों की संख्या समान हो और फिर भी एक ही रंग के दो तार किसी भी पोस्ट से न फैले। (130, यूक्रेन 1989)

प्रांगण में 36 खम्भे हैं, प्रारंभ में किन्हीं दो खंभों के बीच एक तार खींचा जाता है। रोज सुबह स्कूल जाते समय बदमाश वास्या 35 तार काट देता है। हर शाम, इलेक्ट्रीशियन पेट्रोव एक निश्चित पोल से फैले तारों को ठीक करता है। साबित करें कि वास्या इस तरह से कार्य कर सकती है कि एक सुबह एक के बाद एक बर्बरता का कार्य 18 से कम तार रह जाए। (135, ए.वी. पादरी, सेंट पीटर्सबर्ग 2000)

विमान पर 100 अंक अंकित हैं। दो लोग खेलते हैं, बारी-बारी से खेलते हैं। एक चाल में, आप दो बिंदुओं को एक तीर से जोड़ सकते हैं यदि वे पहले नहीं जुड़े हैं। उसी समय, एक तीर खींचना मना है, जिसके प्रकट होने के बाद किसी भी बिंदु से तीर के साथ किसी अन्य तक जाना संभव होगा। जो नियमों का उल्लंघन किए बिना अगला कदम नहीं उठा सकता वह हार जाता है। सही खेल से कौन जीतता है: वह जो पहले चलता है, या उसका साथी?

1 से 100 तक के पूर्णांकों में से कई भिन्न संख्याएँ चुनी गईं। आइए किसी दी गई संख्या की विभाज्यता के संकेतक को उन चुनी हुई संख्याओं की संख्या कहते हैं जिनसे दी गई संख्या विभाज्य है। यह पता चला कि सभी चुनी गई संख्याओं में अलग-अलग विभाज्यता सूचकांक हैं। चुनी जा सकने वाली संख्याओं की सबसे बड़ी संख्या क्या है?

एनवृत्तों को इस प्रकार व्यवस्थित किया जाता है कि उनमें से प्रत्येक का केंद्र दूसरे के ठीक एक के अंदर होता है, और प्रत्येक के अंदर दूसरे में से ठीक एक का केंद्र होता है। सभी नंबर खोजें एनजिसके लिए यह संभव है।

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

रेस्ट हाउस में 1999 वेकेशनर्स हैं। उनमें से कुछ एक दूसरे से परिचित हैं, और कोई दो अनजानछुट्टियों के बीच एक कॉमन फ्रेंड है। सबसे छोटी संभव संख्या क्या है भापपरिचित छुट्टियों?

ग्रह पर 1000 शहर हैं, जिनमें से राज्यों की राजधानियां हैं। कुछ शहर सड़कों से इस तरह जुड़े हुए हैं कि कोई भी सड़क ठीक दो शहरों को जोड़ती है, और किसी भी शहर से किसी भी शहर तक सड़कों द्वारा पहुँचा जा सकता है। वहीं, एक राजधानी से दूसरी राजधानी में जाने के लिए आपको कम से कम 21 सड़कें चलानी होंगी। सिद्ध करें कि ग्रह पर 90 से अधिक राजधानियाँ नहीं हैं।

1997 कीलें बोर्ड में लगी हैं। दोनों बारी-बारी से चाल चलते हैं। इस कदम में यह तथ्य शामिल है कि खिलाड़ी तार से किन्हीं दो कीलों को जोड़ता है जो पहले नहीं जुड़े हैं। वह जो हार जाता है, जिसके चलने के बाद पहली बार किसी कील से तार के द्वारा किसी दूसरे तक जाना संभव हो जाता है। सही खेल से कौन जीतेगा: वह जो पहली चाल चलता है, या उसका साथी?

जुड़ा हुआ ग्राफ जीकिसी भी 18 कोने को हटाते समय जुड़ा रहता है (साथ में उनसे निकलने वाले सभी किनारों के साथ)। चलो कॉल करो कट गया 19 शीर्षों का कोई भी सेट, जिसके हटाने पर ग्राफ़ कनेक्टिविटी खो देता है, और टुकड़ाकोई भी जुड़ा हुआ घटक जो कट हटा दिए जाने पर बनता है। यह ज्ञात है कि 10 से कम शिखर वाला कोई भी टुकड़ा किसी भी खंड में निहित नहीं है। साबित करें कि कट के अंदर कोई टुकड़ा नहीं है।

ग्राफ़ जीजुड़े हुए। चलो कॉल करो कट गयान्यूनतम (समावेशन के संबंध में) शीर्षों का सेट, जिसके हटाने पर (उनसे बाहर जाने वाले सभी किनारों के साथ) ग्राफ़ कनेक्टिविटी खो देता है। यह ज्ञात है कि कटे हुए सिरों को हटाते समय आरकट से कोने एसएक ही जुड़े घटक में दिखाई देते हैं। सिद्ध करें कि कटे हुए शीर्षों को हटाते समय एसकट से कोने आरएक ही जुड़े घटक में दिखाई देते हैं।

चेकर्ड पेपर पर, 49 ग्रिड नोड्स चिह्नित हैं, जो 66 वर्ग के रूप में व्यवस्थित हैं। चिह्नित नोड्स पर सिरों के साथ इकाई खंडों की न्यूनतम संख्या क्या है जिसे खींचा जाना चाहिए ताकि पड़ोसी नोड्स के किसी भी जोड़े के बीच पथ 3 से अधिक न हो?

से एक कंपनी में एनएक व्यक्ति जहां हर कोई कम से कम एक दूसरे से परिचित है, सभी समान रूप से परिचित हैं (ऐसा माना जाता है कि यदि लेकिनपरिचित है में, फिर और मेंपरिचित है लेकिन) साबित करें कि इस कंपनी के सदस्यों में से आप कम से कम चुन सकते हैं एन/3 परिचितों के गैर-अतिव्यापी जोड़े।

एक कंपनी में, प्रत्येक दो व्यक्तियों के ठीक पाँच परस्पर परिचित होते हैं। सिद्ध कीजिए कि परिचितों की संख्या (परिचितों के जोड़े) तीन का गुणज है। ( यू.एम. लाइफशिट्ज़)

एक दौर के टूर्नामेंट में, दो प्रतिभागियों ने पांचवें दौर के बाद प्रतियोगिता छोड़ दी। नतीजतन, टूर्नामेंट में 38 खेल खेले गए। क्या ये दोनों एक-दूसरे की भूमिका निभाने में कामयाब रहे? ( बुल्गारिया, 1982)

एक दौर के टूर्नामेंट में, छह प्रतिभागियों ने छठे दौर के बाद प्रतियोगिता छोड़ दी। नतीजतन, टूर्नामेंट में 67 खेल खेले गए। सिद्ध कीजिए कि ड्रॉपआउट में से कम से कम दो ने आपस में नहीं खेला। ( के.ए. गांठ,)

100-शीर्ष ग्राफ में किनारों की सबसे छोटी संभव संख्या क्या है जैसे कि किन्हीं 11 शीर्षों में से एक है जो उनमें से अन्य 10 से जुड़ा है? ( आर. फेडोरोव)

जुड़े ग्राफ में 2 एनशीर्ष, प्रत्येक शीर्ष की घात तीन है। साबित करें कि इस ग्राफ के किनारों को तीन रंगों से रंगने के तरीकों की संख्या ताकि विभिन्न रंगों के किनारों को प्रत्येक शीर्ष पर अभिसरण किया जा सके 32 से अधिक नहीं एन .

किसी राज्य में 4 एनहवाई अड्डे, प्रत्येक हवाई अड्डा ठीक 3 एयरलाइंस छोड़ता है (एक एयरलाइन दो हवाई अड्डों को जोड़ती है)। किसी भी हवाई अड्डे से आप किसी अन्य हवाई अड्डे के लिए उड़ान भर सकते हैं (संभवतः स्थानान्तरण के साथ)। रहने दो प्रति -बेचने के तरीकों की संख्या सबएयरलाइनों को तीन एयरलाइनों के लिए ताकि प्रत्येक हवाई अड्डे से विभिन्न एयरलाइनों की तीन एयरलाइनें प्रस्थान करें। साबित करें कि प्रति 32 3 एन .

शतरंज के आठ खिलाड़ियों ने एक दौर में टूर्नामेंट खेला। यह ज्ञात है कि शतरंज के खिलाड़ियों की किसी भी तिकड़ी में दो ऐसे खिलाड़ी थे जो एक दूसरे के साथ ड्रॉ खेलते थे। इस टूर्नामेंट में ड्रॉ की सबसे छोटी संख्या क्या हो सकती है?

वर्ग के कोने पर 4 कंप्यूटर हैं जो वर्ग के किनारों पर उनके पड़ोसियों से जुड़े हैं। प्रारंभिक क्षण में, प्रत्येक कंप्यूटर के लिए महत्वपूर्ण समाचार आए (प्रत्येक के लिए - अपना)। हर सेकेंड, एक कंप्यूटर या तो सभी समाचारों को एक पड़ोसी कंप्यूटर को प्रेषित कर सकता है, या पड़ोसी कंप्यूटर से प्रासंगिक जानकारी प्राप्त कर सकता है, या निष्क्रिय रह सकता है। सभी कंप्यूटर कम से कम समय में सिस्टम में सभी समाचार कैसे प्राप्त कर सकते हैं?

एलेनियास की भूमि में एनरहने वाले। वे ब्याज के हलकों में एकजुट होते हैं। प्रत्येक मंडली में ठीक तीन लोग होते हैं, और उनमें से कोई भी दो एक ही समय में ठीक एक मंडली के सदस्य होते हैं। साबित करें कि एनजब 6 से विभाजित किया जाता है, तो शेषफल या तो 1 या 3 होता है।

शिविर में पहुंचे एमलड़के और डीलड़कियाँ। प्रत्येक लड़की 10 से अधिक लड़कों को नहीं जानती है, और प्रत्येक लड़का कम से कम एक लड़की को जानता है। यह पता चला कि प्रत्येक लड़के के पास अधिक लड़कियां हैं जिन्हें वह जानता है कि किसी भी लड़की को वह जानता है कि वह लड़कों को जानता है। साबित करें कि डी 1.1 एम. (डी.वी. कार्पोव)

एक चौदह-हेड्रोन का उदाहरण दें, जिसका प्रत्येक फलक या तो एक वर्ग है या एक नियमित त्रिभुज है? ( हां। करामारेंको)

अंतरिक्ष में 2000 काले बिंदु हैं, जिनमें से कोई भी चार एक ही तल में नहीं हैं। कुछ बिंदु तीरों से जुड़े हुए हैं। यह ज्ञात है कि तीरों का अनुसरण करने और सभी बिंदुओं से गुजरने का कोई रास्ता नहीं है (भले ही एक ही बिंदु से कई बार गुजरना संभव हो)। साबित करें कि कुछ बिंदुओं (कम से कम एक, लेकिन सभी नहीं) को नीले रंग से रंगा जा सकता है ताकि कोई भी तीर नीले बिंदु से काले रंग की ओर न जाए। ( बेलारूस, 1992)

ग्राफ़ में एक फैला हुआ पेड़ है जिसमें बिल्कुल एनलटकते हुए कोने और एक फैले हुए पेड़ के साथ बिल्कुल एमहैंगिंग टॉप्स, एन  क  एम. सिद्ध कीजिए कि इस आलेख में एक फैला हुआ वृक्ष है जिसमें ठीक कलटकती चोटियाँ।

200 लोगों की एक कंपनी में, किन्हीं पांच लोगों को एक गोल मेज पर बैठाया जा सकता है ताकि उनमें से प्रत्येक दो परिचितों के बीच बैठे (यह माना जाता है कि यदि एपरिचित है बी, फिर बीपरिचित है ए) इस कंपनी में परिचितों के जोड़े की सबसे छोटी संख्या क्या हो सकती है?

सिद्ध करें कि प्रत्येक बहुफलक के लिए दो फलकों को लाल और अन्य दो को नीला रंग देना संभव है, ताकि लाल फलकों की भुजाएँ समान हों और नीले फलकों की भुजाएँ समान हों।

जुड़े ग्राफ में 3 ककोने, उन सभी के पास डिग्री 3 है, और प्रत्येक शीर्ष बिल्कुल एक त्रिभुज में शामिल है। ग्राफ के कुछ किनारों को हटा दिया गया है ताकि एक पेड़ प्राप्त हो। सिद्ध कीजिए कि इस वृक्ष में अधिकतम कडिग्री के +2 कोने 1.( डी.वी. कार्पोव)

राज्य में एनशहर और आरसड़कें (प्रत्येक सड़क दो शहरों को जोड़ती है, और आप किसी भी शहर से किसी भी सड़क पर जा सकते हैं)। दूत शहरों में रहते हैं। प्रत्येक वर्ष की शुरुआत में, शहरों में से एक सभी पड़ोसी शहरों (यानी, सड़कों से जुड़ा हुआ) शहरों में एक दूत भेजता है। (ऐसे शहर में इसके लिए पर्याप्त संख्या में दूत होने चाहिए।) कुछ (शून्य से अधिक) वर्षों के बाद, प्रत्येक शहर में उतने ही दूत थे जितने मूल रूप से थे। एक राज्य में दूतों की न्यूनतम संख्या कितनी हो सकती है? ( आई.आई. बोग्डैनोव)

एक ग्राफ दिया गया है जिसके किसी भी शीर्ष की डिग्री कम से कम है क(कहाँ पे क 2)। सिद्ध कीजिए कि इस आलेख में कम से कम लंबाई का एक सरल चक्र है क+1. ()

आतंकवादियों के एक गिरोह में, सभी को कम से कम 10 अन्य लोगों पर देशद्रोह का संदेह होता है। साबित करें कि इस गिरोह में कम से कम 11 आतंकवादियों की पहचान करना और उन्हें नंबर देना संभव है ताकि पहला संदिग्ध दूसरा, दूसरा, तीसरा, ... , अंतिम - अंतिम, और अंतिम - पहला। ( पर आधारितकोज़ेपिस्कोलाई माटेमेटिकाई लापोकी)

एक ग्राफ में, विषम लंबाई के किन्हीं दो सरल चक्रों में कोई उभयनिष्ठ किनारे नहीं होते हैं। सिद्ध कीजिए कि इस ग्राफ के शीर्षों को दो रंगों से रंगा जा सकता है ताकि प्रत्येक शीर्ष एक किनारे से एक ही रंग के अधिकतम एक शीर्ष से जुड़ा हो। एस.एल. बर्लोवी)

देश में 100 शहर हैं। कुछ जोड़े शहर सड़कों से जुड़े हुए हैं, लेकिन कोई भी शहर सभी से नहीं जुड़ा है। किसी भी शहर से किसी भी शहर में जाना संभव है, सड़क पर कॉल करके एक से अधिक शहर नहीं। इस देश में सबसे कम सड़कों की संख्या क्या है? ( )

देश में 25 शहर हैं। कुछ जोड़े शहर सड़कों से जुड़े हुए हैं, लेकिन कोई भी शहर सभी से नहीं जुड़ा है। किसी भी शहर से किसी भी शहर में जाना संभव है, सड़क पर कॉल करके एक से अधिक शहर नहीं। सिद्ध कीजिए कि इस देश में कम से कम 35 सड़कें हैं। ( कोज़ेपिस्कोलाई माटेमेटिकाई लापोकी)

देश में 9 शहर हैं। कुछ जोड़े शहर सड़कों से जुड़े हुए हैं, लेकिन कोई भी शहर सभी से नहीं जुड़ा है। किसी भी शहर से किसी भी शहर में जाना संभव है, सड़क पर कॉल करके एक से अधिक शहर नहीं। क्या इस देश में 13 से ज्यादा सड़कें नहीं हो सकतीं? एस.एल. बर्लोव, डी.वी. कारपोव, कोज़ेपिस्कोलाई माटेमेटिकाई लापोकी पर आधारित)

ग्राफ के सभी शीर्षों की घात जीकम (जहां एन> 2), और इनमें से कोई भी एन+1 दो गैर-आसन्न शीर्ष हैं। चलो कॉल करो खंड मैथासमुच्चय एनजोड़ीवार आसन्न ग्राफ शिखर जीयह ज्ञात है कि किन्हीं दो ब्लॉकों में एक उभयनिष्ठ शीर्ष होता है। सिद्ध कीजिए कि सभी ब्लॉकों में एक उभयनिष्ठ शीर्ष है।( सी.एल. बर्लोवी)

एक पूर्ण ग्राफ के किनारों के साथ एनकोने कई रंगों में रंगे हुए हैं, और रंग कम से कम नहीं हैं एन. सिद्ध कीजिए कि तीन शीर्ष हैं, जिनके बीच के सभी किनारे भिन्न-भिन्न रंगों के हैं। ( पीए कोज़ेवनिकोव)

एक पूर्ण ग्राफ के किनारों के साथ एनकोने कई रंगों में इस तरह से रंगे होते हैं कि प्रत्येक रंग अधिक से अधिक होता है एन- 2 बार। सिद्ध कीजिए कि तीन शीर्ष हैं, जिनके बीच के सभी किनारे अलग-अलग रंगों में रंगे हुए हैं।( एएमएम)

ग्राफ में जीकोने के सेट चुने गए हैं एस 1 , एस 2 , एस 3 प्रत्येक 100 शीर्षों के साथ। यह ज्ञात है कि जब इन तीन सेटों में से किसी के सभी कोने (और उनसे बाहर जाने वाले सभी किनारों) को हटा दिया जाता है, तो ग्राफ के शेष कोने ठीक दो जुड़े घटकों में गिर जाते हैं, और जब कोई 99 कोने हटा दिए जाते हैं, तो ग्राफ जुड़ा रहता है। साबित करें कि सभी सेट में शामिल नहीं हैं एस 1 , एस 2 और एस 3 ग्राफ शिखर जी 6 समूहों में इस तरह विभाजित किया जा सकता है कि एक समूह के शिखर एक ही जुड़े घटक में समाप्त हो जाते हैं जब किसी भी सेट को वर्टेक्स ग्राफ से हटा दिया जाता है एस 1 , एस 2 या एस 3 .(डी.वी. कार्पोव)

किंग मटर के 20 दरबार हैं। उन्होंने एक-दूसरे के खिलाफ साजिश रचते हुए कई गुप्त समाज बनाए। गुप्त पुलिस के मुखिया ने इन सोसायटियों का अध्ययन कर तीन नमूने खोजे। सबसे पहले, किन्हीं दो गुप्त समाजों के लिए, सभी दरबारी जो एक साथ दोनों समाजों के सदस्य हैं, एक गुप्त समाज का निर्माण करते हैं। दूसरे, किन्हीं दो गुप्त समाजों के लिए, सभी दरबारी जो उनमें से कम से कम एक के सदस्य हैं, एक गुप्त समाज बनाते हैं। तीसरे, किसी भी गुप्त समाज के लिए, सभी दरबारी जो इसके सदस्य नहीं हैं, एक गुप्त समाज का निर्माण करते हैं। क्या मटर के दरबार में ठीक 2002 सीक्रेट सोसाइटी हो सकती हैं? ( पूनम 1961, सुधार)

डोडेकाहेड्रॉन के किनारों को बिना दोहराव के 1 से 30 तक गिना जाता है। आइए डोडेकाहेड्रोन के तीन किनारों से बनी टूटी हुई रेखाओं की संख्या गिनें और इस तरह से कि लिंक पर संख्याएँ आरोही क्रम में हों। ऐसी टूटी हुई रेखाओं की न्यूनतम संभव संख्या ज्ञात कीजिए। (आई.आई. बोगदानोव, जी.आर. चेल्नोकोव पोलिश ओलंपियाड -89 . के कार्य पर आधारित है/90 )

1 से 12 तक की संख्याओं को बिना दोहराव के घन के किनारों पर रखा जाता है। आइए क्यूब के तीन किनारों से बनी टूटी हुई रेखाओं की संख्या की गणना करें और इस तरह से कि लिंक पर संख्याएं आरोही क्रम में हों। ऐसी टूटी हुई रेखाओं की न्यूनतम संभव संख्या ज्ञात कीजिए। (पोलैंड-89/90)

20 लोगों की एक कंपनी में किन्हीं तीन के लिए एक ऐसा व्यक्ति होता है जो उन सभी को जानता है। सिद्ध करें कि एक व्यक्ति है जिसके कम से कम नौ परिचित हैं। ( एसएल बर्लोव, आई.आई. बोगदानोव)

10 लोगों की एक कंपनी में किन्हीं तीन के लिए एक ऐसा व्यक्ति होता है जो उन सभी को जानता है। साबित करें कि एक व्यक्ति है जिसके कम से कम छह परिचित हैं।

संगोष्ठी में 100 लोगों ने भाग लिया। इनमें से 15 फ्रेंच हैं, जिनमें से प्रत्येक संगोष्ठी के कम से कम 70 प्रतिभागियों से परिचित है, और 85 जर्मन हैं, जिनमें से प्रत्येक दस से अधिक प्रतिभागियों से परिचित नहीं है। उन्हें 21 कमरों में बसाया गया था। सिद्ध करें कि किसी भी कमरे में परिचितों के जोड़े नहीं हैं। ( वाई. लाइफशिट्स)

कंपनी में 22 एथलीट हैं। एथलीटों के जोड़े जो एक दूसरे के मित्र हैं - चौदह। यह पता चला कि किन्हीं 11 एथलीटों में कम से कम एक जोड़ी दोस्त हैं। साबित करें कि सभी को दो फुटबॉल टीमों में विभाजित किया जा सकता है ताकि दोस्तों की प्रत्येक जोड़ी एक ही टीम में हो। ( 10 प्रमुख लीगों के कार्य को सरल बनाना)

कॉलम 4 . में कचोटियों 3 कपसलियां। यह ज्ञात है कि किसी भी 2 . के बीच कइसके दो शीर्ष एक किनारे से जुड़े हुए हैं। सिद्ध कीजिए कि ग्राफ के शीर्षों को 2 . के दो समूहों में विभाजित किया जा सकता है कप्रत्येक में शीर्ष इस प्रकार हैं कि विभिन्न समूहों के कोई भी दो शीर्ष एक किनारे से जुड़े नहीं हैं। (R.A.Brualdi, S.Mellendorf)

एक शराबी शतरंज का राजा कभी भी एक ही दिशा में एक पंक्ति में दो चाल नहीं चलता है। कोने से शुरू करते हुए, वह 9x9 बिसात के चारों ओर चला, एक बार प्रत्येक कक्ष का दौरा किया, और मूल कक्ष में लौट आया। वह कम से कम कितनी विकर्ण चालें चला सकता है? ( एस.एल. O.Yu की समस्या पर आधारित बेर्लोव। लैनिना, एफएमएल ओलंपियाड नंबर 239, 2002जी.)

देश में 7 शहर हैं, जिनके बीच 7 विमान उड़ान भरते हैं। विमान प्रत्येक शहर से दूसरे शहर के लिए ठीक 1 घंटे के लिए उड़ान भरता है, और लैंडिंग के तुरंत बाद यह अगले शहर के लिए उड़ान भर सकता है (जबकि पारगमन यात्री विमान में रहते हैं)। एक उड़ान अनुसूची बनाएं ताकि कोई भी यात्री, रास्ते में विमान को बदले बिना, हवाई अड्डे पर पहुंचने के 5 घंटे से अधिक समय तक किसी भी शहर से किसी अन्य शहर के लिए उड़ान भर सके। (ग्रॉसमैन ओलंपिक)

घन के पांचों शीर्ष लाल रंग के हैं। क्या यह सच है कि आवश्यक रूप से तीन किनारे ऐसे होते हैं जिनके दोनों सिरों पर लाल सिरे होते हैं?

फेड्या का एक डिस्कनेक्ट ग्राफ है। उन्होंने हर संभव तरीके से इस ग्राफ से एक शीर्ष हटा दिया और प्रत्येक परिणामी ग्राफ को एक अलग कागज के टुकड़े पर खींचा, जिसके बाद उन्होंने कागज के इन सभी टुकड़ों को दीमा को दे दिया। सिद्ध करें कि दीमा इन पत्तों का उपयोग करके मूल ग्राफ को पुनर्स्थापित कर सकती है। ( डी.वी. उलम परिकल्पना के आधार पर कारपोव)

फेड्या में गेंदों वाले कई बॉक्स हैं। वह बक्सों से एक बार में एक गेंद निकालता है, कागज के एक अलग टुकड़े पर संख्याओं का एक सेट लिखता है - प्रत्येक बॉक्स में छोड़ी गई गेंदों की संख्या, अगर कुछ बचा है (यह निर्दिष्ट किए बिना कि कौन सी संख्या किस बॉक्स से मेल खाती है), और फिर गेंद को उसकी जगह पर लौटा देता है। प्रत्येक गेंद को एक बार निकालकर, वह सभी पत्ते दीमा को देता है। सिद्ध कीजिए कि दीमा यह निर्धारित कर सकती है कि प्रत्येक डिब्बे में कितने गुब्बारे हैं। ( डी.वी. कार्पोव)

एन- विषम संख्या। उत्तल शिखर एन-गॉन कई रंगों में रंगे होते हैं ताकि हर दो आसन्न कोने एक अलग रंग के हों। साबित करें कि यह एन-गॉन को अप्रतिच्छेदी विकर्णों द्वारा त्रिभुजों में विभाजित किया जा सकता है, जिनमें से किसी का भी एक ही रंग का सिरा नहीं है। ( कुर्ज़क-1978, 2)

पर एक ग्राफ दिया गया है एनचोटियाँ सिद्ध कीजिए कि इसके सभी किनारों को अधिक से अधिक भागों में विभाजित किया जा सकता है एन 2/4 सेट, जिनमें से प्रत्येक में एक किनारा होता है या एक त्रिभुज होता है। ( बोगदानोव, कारपोवी)

शहर ए, बी, सी उड़ानों से जुड़े हुए हैं। किन्हीं दो शहरों के बीच कम से कम एक उड़ान है और सभी उड़ानें दोतरफा हैं (यदि आप ए से बी तक उड़ान भर सकते हैं, तो वही उड़ान बी से ए तक उड़ सकती है)। इसके अलावा, यह ज्ञात है कि बिंदु ए से बिंदु सी (बी में परिवर्तन वाले मार्गों सहित) तक पहुंचने के तरीकों की कुल संख्या 11 है, और बिंदु ए से बिंदु बी तक पहुंचने के तरीकों की कुल संख्या (मार्गों सहित) C पर परिवर्तन) 13. इन शहरों के बीच नॉन-स्टॉप उड़ानें हैं?

एक चेकर्ड वर्ग दिया गया है जिसकी भुजा में शामिल है एननोड्स। एक गैर-वापसी पथ किनारों के साथ एक पथ है, जिसका प्रतिच्छेदन किसी भी क्षैतिज या ऊर्ध्वाधर रेखा के साथ एक खंड, एक बिंदु या एक खाली सेट है। गैर-पुनरावर्ती पथों की सबसे छोटी संख्या क्या है जो सभी शीर्षों को कवर कर सकती है? ( आई. पुष्करेव, आई. बोगदानोव, जी. चेल्नोकोव,)

एक जुड़ा हुआ ग्राफ दिया गया है जो किसी भी शीर्ष को हटा दिए जाने पर जुड़ा रहता है। यह ज्ञात है कि इसका एक त्रिभुज है। प्रत्येक शीर्ष पर, एक को छोड़कर, एक टोकन होता है (सभी टोकन अलग-अलग होते हैं)। इसे एक टोकन को एक खाली से सटे एक शीर्ष से एक खाली में स्थानांतरित करने की अनुमति है। सिद्ध कीजिए कि इस प्रकार की क्रियाओं से किसी भी विन्यास से चिप्स का कोई विन्यास प्राप्त किया जा सकता है। ( एम.माज़िन)

शहर में, 10 सड़कें उत्तर से दक्षिण की ओर जाती हैं, और 11 पश्चिम से पूर्व की ओर, 110 चौराहों का निर्माण करती हैं। महापौर के आदेश से शहर में कोई भी बस मार्ग दो दिशाओं (पूर्व-दक्षिण, पूर्व-उत्तर, पश्चिम-दक्षिण या पश्चिम-उत्तर) से अधिक नहीं जा सकता है। क्या शहर के सभी चौराहों को सात बस मार्गों से जोड़ना संभव है? (आई। पुष्करेव, आई। बोगदानोव, जी चेल्नोकोव के आधार पर)

उत्तल पॉलीहेड्रॉन में सबसे छोटी संख्या क्या हो सकती है, जिनमें से तीन चेहरे पेंटागन हैं? ( यूएसएएमटीएस 2003)