सूक्ति और रंगीन टोपी की चुनौती

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

जो लोग रुचि रखते हैं और जो इस समय हल करने की कोशिश नहीं करना चाहते हैं, कृपया बिल्ली के नीचे स्वागत करें। लेख समस्या और उसके "समाधान" की चर्चा होगी। (गणित प्रेमियों के लिए, मैं आपको कोशिश करने और हल करने की सलाह देता हूं)।

भाग 1/4। कुछ विचार।

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

भाग 2/4। लेखक का समाधान।

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

हां, घटनाओं के ऐसे मोड़ ने मुझे परेशान कर दिया, और मुझे अपने दावे का बचाव करने के लिए अपने तर्क में असंगतता की तलाश करनी पड़ी कि कोई समाधान नहीं था।

भाग 3/4। क्या गलत है

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

तब मैंने यह सोचना शुरू किया कि सूक्ति कैसे समझ सकती है कि वर्तमान अनुक्रम किस वर्ग का है। क्या उन्हें सभी वर्गों के माध्यम से क्रमबद्ध करना होगा और तुलना करना होगा कि समस्या क्या हो सकती है, क्योंकि कक्षाओं की निरंतरता के माध्यम से क्रमबद्ध करने के लिए पर्याप्त नहीं है, इस धारणा के तहत कि गैर-शून्य समय लगता है ...
लेकिन मैंने आपको बहुत अधिक भ्रमित नहीं किया है, और पहले से ही वह ढेर हो गया है। तथ्य यह है कि मैंने आपको केवल धोखा दिया है। किसको मिला? आप किसी वर्ग के सबसे छोटे लेक्सिकोग्राफिक तत्व का चयन नहीं कर सकते।
उदाहरण के लिए, एक वर्ग, जिसमें सभी नीले रंग के कैप 1, 1, 1, 1, 1, 1, 1 का अनुक्रम होता है ... इसमें अनुक्रम भी होंगे:
-1, 1, 1, 1, 1, 1, ...
-1, -1, 1, 1, 1, 1, ...
-1, -1, -1, 1, 1, 1, ... जो एक लेने के लिए, वहाँ एक lexicographically छोटे अनुक्रम है। इसके अलावा, किसी भी वर्ग के बारे में भी यही कहा जा सकता है - कोई भी अनुक्रम सबसे छोटा नहीं है, आप इसमें पहली इकाई पा सकते हैं और इसे -1 से बदल सकते हैं, और भी छोटा हो सकता है। यह पता चला है कि इस तरह के एक न्यूनतम केवल कक्षाओं में से एक में मौजूद है - जिसमें -1, -1, ... सभी लाल कैप का क्रम है।
वापस आ जाओ।

भाग 4. पसंद का स्वयंसिद्ध।

सवाल उठता है: क्या इस निर्णय में इसके बिना करना संभव है? अब विश्लेषण करते हैं।
हमारे वर्ग क्या हैं? आइए खंड से संख्या के रूप में सभी अनुक्रमों का प्रतिनिधित्व करते हैं [0; 1]। हम मानते हैं कि कैप संख्या 0 और 1 हैं, और अनुक्रम बाइनरी सिस्टम में नंबर 0, एबीडी ... है। हम अनुक्रम का हिस्सा खो देंगे, क्योंकि, उदाहरण के लिए, उनमें से दो हैं:
0.011111 ... और 0.100000 ... समान अंश 1/2 परिभाषित करें। लेकिन यह बहुत डरावना नहीं है, ऐसे बहुत कम टकराव हैं (केवल गणना योग्य)। लेकिन कुछ अनुक्रम प्रत्येक संख्या के अनुरूप होंगे, इसलिए यह 0/1 से सभी अनुक्रमों और खंड के सभी संख्याओं के बीच एक-से-एक पत्राचार है [0; 1]।
एक खंड पर हमारी कक्षाएं कैसी दिखती हैं? भयंकर रूप से, प्रत्येक वर्ग एक गणनीय सघन समुच्चय है। इसका मतलब यह है कि किसी भी वर्ग ए और संख्या x के लिए [0 से; 1], वर्ग A में epsilon> 0 एक संख्या होगी जिसकी x से दूरी epsilon से कम है।
इसके अलावा, यदि हम प्रत्येक वर्ग के प्रतिनिधियों को चुनते हैं, तो वे एक विशिष्ट सेट बनाते हैं, जो लेब्सगेग मापने योग्य नहीं है। मैं इस तथ्य का प्रमाण एक छोटे से विकिपीडिया लेख में पढ़ने का प्रस्ताव करता हूं। विटाली सेट का निर्माण बहुत ही समान तरीके से किया गया है, और जब शब्द "सभी तर्कसंगत संख्याओं के लिए" (पारियों के बारे में) की अस्थिरता को साबित करता है, तो आपको "फॉर्म 2 के सभी भिन्नों के साथ बदलना चाहिए" n "(विटाली सेट में, एक वर्ग की संख्या एक तर्कसंगत संख्या से भिन्न होती है, लेकिन मेरे पास है) दो की नकारात्मक शक्तियों का एक निश्चित योग पर, यानी निर्दिष्ट प्रकार के एक अंश पर)।
इस बिंदु पर, आपत्ति में टकराव के साथ समस्या, जिसे मैंने थोड़ा अधिक नजरअंदाज कर दिया था, को जाम कर दिया जाता है, क्योंकि काउंटेबल सेट बैक-अगल ऐड-टू-टेक लेबेसेग की औसत दर्जे को प्रभावित नहीं करता है।
ठीक है, किसी को पता है, लेकिन कोई एक ही विकिपीडिया लेख में पढ़ सकता है कि लेबेसेग माप के बिना बंधे सेट का निर्माण हमेशा पसंद के स्वयंसिद्ध पर आधारित होता है। नतीजतन, लेखक का निर्णय इस स्वयंसिद्ध पर बहुत अधिक निर्भर करता है, और इसके बिना यह सच नहीं है।
यह पता चला है कि हमारे गरीब gnomes जानते हैं कि कक्षाओं के प्रतिनिधियों के लिए एक विकल्प फ़ंक्शन है (यदि वे जेडएफसी प्रमेय से सहमत हैं, तो निश्चित रूप से), लेकिन वे इन प्रतिनिधियों को समान रूप से चुनने में सक्षम नहीं होंगे, क्योंकि इस फ़ंक्शन का वर्णन करना असंभव है।

उपसंहार।

क्या मैंने लेखक की बेवफाई को साबित किया? मुझे ऐसा लगता है। समस्या का कथन है कि सूक्ति कैसे सहमत होती है। विकल्प के स्वयंसिद्ध की आवश्यकता असमान रूप से कहती है कि समाधान में "कैसे" का उत्तर नहीं है और न ही हो सकता है।
क्या समस्या का कोई हल है? इसकी अनुपस्थिति को साबित करना बहुत मुश्किल काम है, और यह संभव नहीं है कि सूक्ति की समानता और सूचनाओं के आदान-प्रदान करने की क्षमता की कमी से बेहतर कुछ हो। यह मेरे लिए पर्याप्त है। अगर किसी को कुछ सख्त आता है, तो कृपया साझा करें
यह सब क्यों है? जैसा कि मैंने कहा, मेरी राय में, इस हब के पाठकों की दिलचस्पी हो सकती है। और मैं, बदले में, समुदाय के साथ समस्या पर चर्चा करने में बेहद दिलचस्पी रखता हूं। और फिर भी, आप लेख को व्यावहारिक (जहाँ तक यह व्यावहारिक हो सकता है) पर विचार कर सकते हैं और संक्षिप्त नाम ZFC और संबंधित समस्याओं में अंतिम पत्र की एक सुलभ मिनी-समीक्षा कर सकते हैं।
आपका दिन शुभ हो!