उपक्रम वाचनमात्र उपलब्ध आहे.
कोडे : ओळखा तुमची टोपी
धक्का
April 7, 2011 - 6:37 am
१०० कैदी आहेत. त्यांना बरोबर १ तासानंतर एका सरळ रांगेत उभे केले जाणार आहे.
१००वा कैदी सामोरचे ९९ कैदी पाहू शकतो , ९९ वा पुढचे ९८ .... ५० वा पुढचे ४९ .. १ल्याला कुणीच दिसणार नाही इत्यादी.
सर्व १०० जणांच्या डोक्यावर पांढरी किंवा काळी टोपी ठेवली जाईल, ती अशी की कुणालाच आपल्या डोक्यावरची टोपी दिस्नार नाही परंतू आप्ल्या
सगळ्या समोरच्यांच्या डोक्यावरची टोपी दिसेल (कैदी नं १०० ला पुढच्या ९९ कैद्यांच्या टोप्या दिसतील... कैदी नं २ ला फक्त १ ची टोपी दिसेल इ.)
सुरवातीला कुठल्या रंगाच्या टोप्या किती हे कुणालाच माहित नाही आहे.
कैदी नं १०० पासून स्वत:च्या डोक्यावरची टोपी कुठल्या रंगाची ते विचारणी सुरू होइल. जर उत्तर चुकले तर आजन्म कारावास, बरोबर आले तर सूटका. कुठल्या कैद्याने काय उत्तर दिले हे सर्वांना आइकू जाएल, परंतू ते चुकले का बरोबर ते नाही कळनार.
एकदा का रांगेत उभे केले की टोपीचा कलर सोडून बाकी काही बडबड करायला बंदी आहे.
१ तासामधे त्या १०० कैद्यांना त्यांची स्ट्राटजी बनवायची आहे की जास्तीत जास्त कैदींची सुटका होइल.
त्यांनी कूठली योजना बनवावी जेणेकरून जास्तीत जास्त कैदी सुटतील?
(कृ. उत्तरे इथेच दिलीतरी हरकत नाही. ह्या कोड्याची बरीच उत्तरे असू शकतील. ज्या पद्धतीने जास्त कैदी वाचतील ती पद्धत श्रेष्ठ )
दुवे:
Comments
विनंती: उत्तरे कृपया पांढर्‍या रंगात द्यावी
मला खूप आवडलेल्या कोड्याचे स्मरण करून दिल्याबद्दल धन्यवाद. उत्तरासाठी आवश्यक युक्ती मला सुचण्यापूर्वीच मित्राने मला उत्तर सांगितले होते. :(
--
उत्तरः ९९.५
इंगित: पॅरिटीची संकल्पना वापरून ९९ कैदी सुटू शकतील.
पूर्ण उत्तर: १०० व्या कैद्याला दिसणार्‍या काळ्या टोप्यांची संख्या जर सम असेल तर तो 'काळी' असे उत्तर देईल, जर त्याला दिसणार्‍या काळ्या टोप्यांची संख्या जर विषम असेल तर तो 'पांढरी' असे उत्तर देईल अशी मूलभूत योजना असेल.
१०० व्या कैद्याच्या उत्तरावरून ९९ व्या कैद्याला स्वतःची टोपी नक्की ओळखता येईल, उदा., पहिल्या ९९ मध्ये सम काळ्या टोप्या असल्याचे १००व्याने सांगितले आणि ९९ ला मात्र विषम काळ्या टोप्या दिसत असतील तर तर त्याला समजेल की त्याची स्वतःची टोपी काळी आहे. जर त्यालाही समच काळ्या टोप्या पुढे दिसल्या तर तो 'पांढरी' हे उत्तर ओळखेल. पहिल्या ९९ मध्ये विषम काळ्या टोप्या असल्याचे १००व्याने सांगितले आणि ९९ ला मात्र समच काळ्या टोप्या दिसत असतील तर तर त्याला समजेल की त्याची स्वतःची टोपी काळी आहे. जर त्यालाही विषमच काळ्या टोप्या पुढे दिसल्या तर तो 'पांढरी' हे उत्तर ओळखेल.
अशा प्रकारे, १००व्या कैद्याव्यतिरिक्त सर्वच कैदी स्वतःच्या टोपीचा रंग ओळखू शकतील. १०० व्याचा अंदाजही ५०% वेळा योग्य ठरेल ;)
मस्तच !
सहीच. या पेक्षा चाणाक्ष उत्तर असू शकेल असं वाटत नाहीये.
धन्यवाद. एक वेगळी कल्पना मला मिळाली.
---------------------
वाद विवादात "जो शेवटचं वाक्य बोलतो / लिहीतो तो जिंकला" असा समज is = गैरसमज
-धनंजय कुलकर्णी
उत्तम
उत्तम कोडे, रिकामटेकडा ह्यांचे उत्तम उत्तर. :)
माझे उत्तर थोडे अगणितीय प्रकारचे आहे.
एकाचा बळी जाण्याची शक्यता आहे. मागचा कैदी पुढच्या कैद्याच्या टोपीचा रंग ओळखेल ह्या रीतीने ९९ कैदी तरी सुटतील, पण प्रथम रंग सांगणाऱ्या १०० व्या कैद्याला स्वतःच्या टोपी एवजी समोरच्याच्या टोपीचा रंग सांगावा लागेल. तोच रंग त्याच्या टोपीचा असण्याची शक्यता कमी आहे. (इथे रिकामटेकडा ह्यांचे उत्तर ५०% शक्यतेची हमी देतो, म्हणून ते जास्त अचूक आहे)
जरा वेगळे :
तुमच्या उत्तरात फक्त ५० कैदी वाचू शकतील , ९९ नाही.
स्पष्टीकरणः
९९ वा हा ९८ च्या डोक्यावरची टोपी कुठली हे न सांगता १०० ने जे ९९च्या डोक्यावरची जी टोपी आहे असेअ सांगीतले आहे ते सांगेल.
म्हणजेच ९९ चे उत्तर बरोबर येयील.
९८ मात्र ९७ च्या डोक्यावरची टोपी कुथली हे सांगेल , परंतू स्वत:च्या डोक्यावरची टोपी कुठली हे न सांगीतल्याने तो सुटनार नाही.
९७ मात्र ९८ ने जे सांगीतले आहे ते सांगेल. ....
असे करून प्रत्येकी २ कैद्यांमधे १ कैदी वाचू शकतो.
---------------------
वाद विवादात "जो शेवटचं वाक्य बोलतो / लिहीतो तो जिंकला" असा समज is = गैरसमज
-धनंजय कुलकर्णी
चुक मान्य
अरे खरेच की. :) हो चुक मान्य.
दुरुस्ती
तुमच्या पद्धतीनुसार साधारणतः ७५ कैदी वाचतील कारण जे ५० कैदी समोरच्याचे उत्तर सांगतील त्यांपैकी काहींच्या स्वतःच्या टोप्यांचाही रंग तोच असेल. या 'काही' चे अपेक्षित मूल्य २५ आहे.
२५% असू शकेल का?
मला या ठीकाणी असे वाटते :
उदा. घरात एक खिडकी आहे. आत्ता ती उघडी आहे. तुम्हाला एक नाणं दिलं आहे. खिडकी जर उघडी असेल तर तुम्हला
छापा असे म्हणायचे आहे आणि बंद असेल तर काटा असे.
तुमचा मित्र तिथे आला आहे. त्याच्याकडे सुद्धा नाणे आहे.तो मात्र नाणेफेक करताना जेंव्हा पहिजे तेंव्हा छापा / काटा म्हणू शकतो.
तुम्ही मात्र जर खिडकी उघडी असेल तर छापा आणि बंद असेल तर काटा असेच म्हणायचे आहे.
खिडकीची उघडझाप करायला अजून एक तिसरी व्यक्ती आहे ती वाटेल तेंव्हा उघडझाप करू शकते.
प्रश्न :
१. >
नाणेफेक होते (खिडकी बंद केली आहे).
इथे तुमच्या मित्राची नाणेफेक जिंकण्याची शक्यता जास्त आहे की तुमची ?
२. पुन्हा नाणेफेक होते (खिडकी अजून बंदच आहे)
इथे तुमच्या मित्राची नाणेफेक जिंकण्याची शक्यता जास्त आहे की तुमची ?
सेम सिचूएशन टोप्यांना लावा. समोरच्याची टोपी पांढरी /काळी असू शकते. त्याचीच टोपी तुमची असेल ह्याची
शक्यता किती आहे(लक्शात घ्या की तुमची टोपी काळी अथवा पांढरी ह्याची शक्यता ५०% आहे) ?
मला इथे कंडीशनल शक्यता वाटत असून ह्याचे उत्तर २५% असे आहे असे वाटत आहे. तुम्हाला काय् वाटते.
---------------------
वाद विवादात "जो शेवटचं वाक्य बोलतो / लिहीतो तो जिंकला" असा समज is = गैरसमज
-धनंजय कुलकर्णी
तरीही!
असे समजा की १०० वा कैदी आणि ९९ वा कैदी यांच्यासोबत एकच प्रयोग १०० वेळा केला. त्यापैकी २५ वेळा दोन्हींच्या टोप्या काळ्या असतील, २५ वेळा दोन्हींच्या टोप्या पांढर्‍या असतील आणि ५० वेळा एकाची टोपी पांढरी आणि दुसर्‍याची काळी असेल. टोप्यांचा रंग समान असलेल्या एकूण ५० प्रयोगांमध्ये १०० व्या कैद्याचे उत्तर 'योग्य' ठरेल.
उत्तर
उत्तर फार आवडले.
प्रमोद
हेच सुचले
छान
छान उत्तर
रिकामटेकडा यांचं उत्तर खूप आवडलं. प्रत्येक कैद्यासाठी आपलं अचूक उत्तर हीच पुढच्यासाठी निष्कर्ष काढण्यासाठी पुरेशी माहिती असणं हे साधलेलं आहे. मस्त.
राजेश
द्रौपदीचे सत्त्व माझ्या लाभु दे भाषा-शरीरा
भावनेला येउं दे गा शास्त्र-काट्याची कसोटी
कोडे सोडवता येत नाही.
अटी-
१) सर्व १०० जणांच्या डोक्यावर पांढरी किंवा काळी टोपी ठेवली जाईल.
२) सुरवातीला कुठल्या रंगाच्या टोप्या किती हे कुणालाच माहित नाही आहे.
ह्या दोन अटींमुळे हे कोडे सोडवता येत नाही.
स.स.
(समस्या समाधान)
सुरवातीला कुठल्या रंगाच्या टोप्या किती हे कुणालाच माहित नाही आहे. >>
सुरवातीला म्हणजे - टोप्या ठेवण्याअगोदर
कुठल्या रंगाच्या टोप्या किती- म्हणजे २० काळ्या आणी ८० पांढर्‍या किंवा ३४ पांढर्‍या आणी ६६ काळ्या किंवा अजून काही .. अशा प्रकारची माहिती दिलेली नाही.
टोप्यांच्या बहुदा कोड्यांमधे सुरवातीला सांगीतले जाते की "रे बाबा .. १० काळ्या आणि ५ पांढर्‍या टोप्या आहेत".
हा प्रश्न कुणी विचारू नये म्हणून मी ती ओळ लिहीली आहे.
संक्षीप्त :
२) सुरवातीला कुठल्या रंगाच्या टोप्या किती हे कुणालाच माहित नाही आहे.
-- पांढर्‍या-काळ्या टोप्यांचा प्रत्येकी काउंट माहित नाही.
---------------------
वाद विवादात "जो शेवटचं वाक्य बोलतो / लिहीतो तो जिंकला" असा समज is = गैरसमज
-धनंजय कुलकर्णी
छान कोडे
रिकामटेकडा यांचे उत्तरही झकास आहे. त्या उत्तराशी सहमत
एक अगणितीय उत्तर, दोन गणिती उत्तर
१०० व्या कैद्याने ९९ व्या कैद्याच्या टोपीचा रंग सांगावा. समजा काळा.
९९ व्या कैद्याने आपल्या टोपीचा रंग सांगावा - पण ९८ व्या कैद्याची टोपी पांढरी असेल तर तो शब्द लांबवून सांगावा. ९८ व्याची जर काळीच असेल तर तो भरकन सांगावा. हेच सगळ्यांनी केलं तर किमान ९९ कैदी सुटतील.
आता गणिती उत्तरं .
१. १०० ते ५१ या कैद्यांनी ५० ते १ या कैद्यांच्या टोप्यांचे रंग सांगावे. म्हणजे किमान ५० कैदी निश्चित सुटतील. १०० ते ५१ मधील सुमारे २५ सुटतील.
२. दर दहा कैद्यांमध्ये एक बळीचा कैदी ठेवायचा. तो पुढच्या नवांचे रंग बघून त्यातले अधिक कुठचे आहेत हे सांगणार. मग त्या सगळ्यांनी तोच रंग सांगायचा. म्हणजे १०० ने ९९ ते ९१ मधील, ९० ने ८९ ते ८१ मधील... बहुसंख्य रंग सांगायचा. या रीतीने पुन्हा किमान ५० निश्चितच सुटतात. पण वेगवेगळ्या डिस्ट्रिब्यूशन्समध्ये ७५ च्या वर सुटण्याची शक्यता आहे. हा बळीचा कैदी दहात एक ऐवजी चारात एक असेल तर अधिक कैदी सुटतील असा अंदाज आहे. निश्चित सांगण्यासाठी थोडी गणितं करावी लागतील.
राजेश
द्रौपदीचे सत्त्व माझ्या लाभु दे भाषा-शरीरा
भावनेला येउं दे गा शास्त्र-काट्याची कसोटी
आश्चर्य
बकरा दोनांत एक असो वा शंभरात एक, सर्वच पद्धतींमध्ये ७५ हेच उत्तर मिळते (५० नक्की आणि २५ एक्स्पेक्टेड) असे निरीक्षण सापडले आणि त्याचे मला आश्चर्य वाटले.
शंभरात एक बकरा असल्यास ९९.५ सुटतात
हे वरती तुमचेच उत्तर पटण्यासारखे आहे. त्याच प्रकारे १०पैकी एक बकरा असल्यास ९० नक्की ५ कदाचित सुटतात.
शंका
शंभरात एक बकरा असतो तेव्हा राजेश यांच्या पद्धतीत तो अधिक असलेल्या टोप्यांचा रंग सांगेल आणि सगळेजण तेच उत्तर देतील. त्यामुळे, ५० लोक नक्कीच सुटतील आणि बाकीच्यांपैकी २५ सुटणे एक्स्पेक्टेड आहे.
तसं नाही...
माझं उत्तर रिकामटेकडा यांच्यापेक्षा वेगळं आहे. माझं स्टॅटिस्टिकल स्वरूपाचं आहे. माझ्या बकऱ्याची व त्यांच्या बकऱ्याची स्ट्रॅटेजी वेगवेगळी आहे. त्यामुळे माझ्या उत्तरात १० बकरे असतील तरी ते पुढच्या नऊपैकी खात्रीलायकरीत्या फक्त ५ जणांना सोडवू शकतात. चारात एक बकरा ठेवला (माझ्या पद्धतीने) तर ७५ पेक्षा अधिक सुटतील असं वाटलं होतं. पण
३ एकाच रंगाचे - शक्यता ०.२५
२ एका रंगाचे - शक्यता ०.७५
सुटलेले लोक - (०.७५ + १.५)*२५ = २.२५ * २५ = ५६.२५
पंचवीस बकऱ्यांपैकी १२.५. म्हणजे सगळे मिळून = ६८.७५
हे अर्थातच काळे पांढरे समान असताना. एक रंग अधिक असेल तर हा आकडा वाढेल. मला वाटतं स्टॅटिस्टिकल स्ट्रॅटेजींमध्ये जितके जास्त बकरे ठेवाल तितकी वेगवेगळ्या वितरणांमध्ये अधिक नियमितपणाने जास्त माणसं सोडवता येतील.
पण कुठचीही स्टॅटिस्टिकल पद्धती वापरली तर उत्तर बहुतेक वेळा ७५ वरच कन्व्हर्ज होतं (काही खात्रीलायक व काही एक्स्पेक्टेड धरून) हे गमतीदार आहे. त्यातही खात्रीलायक ५० च्या वर जात नाहीत. इन्फर्मेशन थिअरीचा काहीतरी गुणधर्म आपण तपासून पहातो आहोत बहुतेक.
राजेश
द्रौपदीचे सत्त्व माझ्या लाभु दे भाषा-शरीरा
भावनेला येउं दे गा शास्त्र-काट्याची कसोट
+१
असेच म्हणतो.
--
मला स्वतःला सुचलेले उत्तर:
पुढच्या न-log(न) जणांपैकी एकूण काळ्या टोप्यांची संख्या सर्वांना सांगण्यासाठी सर्वात मागच्या log(न) लोकांनी स्वतःचे बिट खर्चले तर न-(log(न)) खात्रीचे आणि (log(न)/२) एक्स्पेक्टेड असे एकूण न-(log(न)/२) कैदी सुटू शकतील. म्हणजे, १०० पैकी ९६.५ असे उत्तर मिळेल.
अच्छा मग रिकामटेकडा यांच्याशी सहमत
अच्छा मग रिकामटेकडा यांच्याशी सहमत.
(इन्फोर्मेशन थियरीबद्दल सुद्धा विचार करून लिहावे लागेल. पण अनुमानधपक्याने लिहायचा मोह सुटत नाही. बहुधा इन्फर्मेशन थियरीचा कुठलाही खोल प्रकार येथे नाही. एक्पेक्टेड व्हॅल्यूच्या दोन्ही बाजूला "बाय सिमेट्री" ७५% येते असे वाटते.)
उपक्रम दिवाळी २००८:सांघिक परीक्षा
मराठी असे आमुची मायबोली तिला बैसवूं वैभवाच्या शिरी |
***********************************
उपक्रम दिवाळी २००८ या अंकात" सांघिक परीक्षा" हे कोडे याच स्वरूपाचे आहे.त्यात सोळा जण आहेत एव्हढेच.उत्तरही दिले आहे. संख्या न असेल तर (न-१) जण आपल्या टोपीचा रंग अचूक सांगू शकतील अशी रणनीती आखता येते.
होय की!
धन्यवाद. ते कोडे अधिक नेटक्या नियमांनी आणि गेम थिअरीला अनुसरून बनविलेले आहे.