Кіріспе
Логикалық жұмбақ
Индукциялық жұмбақтар – индукция принципімен бірге шешімі дамитын көп агенттік ойлаудың мысалы. Жұмбақтың сценарийінде әрқашан бірдей ойлау қабілетіне ие және бірдей ойлау қадамдарынан өтетін бірнеше қатысушы болады. Индукция принципіне сәйкес, ең қарапайым жағдайға берілген шешім келесі күрделі жағдайдың шешімін анықтайды. Индукциялық жұмбақтың ең қарапайым жағдайы шешілгеннен кейін, бүкіл жұмбақ одан әрі шешіледі. Осы жұмбақтардың ерекше белгілеріне кез келген жұмбақ жатады, онда әрбір қатысушы басқа барлық қатысушылар туралы белгілі бір ақпаратқа (әдетте, ортақ білім ретінде) ие, бірақ өздері туралы емес. Сонымен қатар, қатысушылар бір-бірінің интеллектына сенім арта алатынын көрсететін белгілі бір түйсік әдетте беріледі – олар теориялық ойлауға қабілетті («әрбір қатысушы modus ponens біледі» дегені ортақ білім). Сондай-ақ, қатысушының әрекетсіздігі – бұл қатысушының білімінің жетіспеуі туралы тікелей хабарлама, ол әрекетсіздікті байқаған барлық қатысушылар үшін ортақ білімге айналады. «Балшықты балалар» жұмбағы – эпистемиялық логика бойынша ғылыми әдебиетте ең көп кездесетін индукциялық жұмбақ. «Балшықты балалар» жұмбағы – белгілі даналар немесе адал әйелдер/ерлер жұмбақтарының бір түрі. «Қалпақ» жұмбақтары – индукциялық жұмбақтың 1961 жылға дейін жететін түрлері. Көптеген нұсқаларында «қалпақ» жұмбақтары түрмедегілер туралы айтылады. Басқа жағдайларда «қалпақ» жұмбақтары дана адамдармен байланысты сипатталады.
Сипаттама
Бір топ назарлы балаларға араларының кейбіреуінің беттері лайлы екені айтылады. Әр бала өзгелердің беттерін көре алады, бірақ өз беті лай екенін біле алмайды. Балаларға лай беттері барлар алға қадам жасау керектігі ескертіледі, бірақ таза беті бар бала алға шықса жазаланады. Үш санауға дейін, беті лай деп ойлаған әрбір бала бірден алға қадам жасауы керек; ешқандай жолмен екінші біреуге сигнал берген бала жазаланады. Егер лай беті бар баланың бірі де алға қадам жасаса, процедура қайталанады.
Логикалық шешім
Егер әр баланың – және әрқайсысының басқалардың – толық логикасы бар деп есептесек, беті сазды балалар бірдей кезеңде алға қадам басады. Балалардың ақпараты әртүрлі, олардың өзінің беті сазды ма, жоқ па, соған байланысты. Әр топ мүшесі сазды беттерді көреді және егер олар ғана сазды болса, сол балалар белгілі бір кезеңде алға шығатынын біледі. Егер мұндай болмаса, әрбір мүше өзі де топқа жататынын біліп, сол кезеңде алға қадам жасайды. Топқа жатпайтын әрбір бала сазды беттерді көреді және кем дегенде белгілі бір кезеңге дейін ешкімнің алға қадам жасамайтынын күтеді. Екі бала бар делік, Алиса мен Боб, және тек Алисаның ғана беті сазды. Алиса «кейбір» балалардың беті сазды екенін біледі, бірақ ешкімнің беті саз емес, яғни оның өзінің беті саз болуы керек, сондықтан ол бірінші кезеңде алға қадам басады. Боб Алисаның сазды бетін көріп, бірінші кезеңде өзінің беті сазды ма, жоқ па, білуге мүмкіндігі жоқ, себебі Алиса алға қадам баспағанша (өзінің беті таза екенін көрсетеді). Егер Алиса да, Боб та сазды болса, екеуі де Бобтың орнында болады: бірінші кезеңде екеуі де алға қадам баса алмайды. Бірақ екінші кезеңде Боб Алисаның өзінің беті сазды екенін көрген болуы керек (себебі ол бірінші кезеңде алға қадам баспады), сондықтан ол екінші кезеңде алға қадам басады. Осы логиканы қолданып, Алиса да екінші кезеңде алға қадам басады. Үшінші бала бар делік, Чарли. Егер тек Алисаның ғана беті сазды болса, ол сазды беттерді көрмейді және бірінші кезеңде алға қадам басады. Егер Алиса мен Бобтың екеуінің де беті сазды болса, бірінші кезеңде екеуі де алға қадам баса алмайды, бірақ екінші кезеңде екеуі де біледі, екіншісі сазды бет көрген (ол Чарлидің беті емес екенін көреді), сондықтан олардың өзінің де беті саз болуы керек, және екеуі де екінші кезеңде алға қадам басады. Чарли екі сазды бетті көріп, екінші кезеңде өзінің беті сазды ма, жоқ па, білмейді, себебі Алиса мен Боб екеуі де алға қадам баспағанша (өзінің беті таза екенін көрсетеді). Егер үшеуінің де беті сазды болса, әрқайсысы Чарлидің орнында болады: егер екі адам екінші кезеңде алға қадам баспаса, әрқайсысы екіншісінің екі сазды бетін көретінін біледі, яғни олардың өзінің де беті саз болуы керек, және әрқайсысы үшінші кезеңде алға қадам басады. Сазды балалардың санына байланысты, олардың үшінші кезеңде алға қадам басатынын дәлелдеуге болады.
Assume there are two children, Alice and Bob, and that only Alice is muddy Alice knows that "some" children have muddy faces but that nobody else's face is muddy, meaning that her own face must be muddy and she steps forward on turn one. Bob, seeing Alice's muddy face, has no way of knowing on turn one if his own face is muddy or not until Alice steps forward (indicating that his own face must be clean). If both Alice and Bob are dirty , each is in the position of Bob when : neither can step forward on turn one. However, by turn two Bob knows that Alice must have seen that his face is muddy (because she did not step forward on turn one), and so he steps forward on turn two. Using the same logic, Alice also steps forward on turn two. Assume that there is a third child, Charlie. If only Alice is muddy , she will see no muddy faces and will step forward on turn one. If both Alice and Bob are muddy , neither can step forward on turn one but each will know by turn two that the other saw a muddy face—which they can see is not Charlie's—so their own face must be muddy and both will step forward on turn two. Charlie, seeing two muddy faces, does not know on turn two whether his own face is muddy or not until Alice and Bob both step forward (indicating that his own face is clean). If all three are muddy , each is in the position of Charlie when : when two people fail to step forward on turn two, each knows that the other sees two muddy faces meaning that their own face must be muddy, and each steps forward on turn three. It can be proven that muddy children will step forward at turn .
Ойын теориясы бойынша шешім
Балшықты балалар жұмбағын ойын теориясынан кері индукция қолдану арқылы да шешуге болады. Әрбір үйленген әйел Патшалықтағы өзінің күйеуінен басқа барлық ер адамдардың адалдығын біледі, ал әдеп бойынша ешбір әйелге күйеуінің адалдығы туралы айтуға болмайды. Сондай-ақ, Патшалықтағы кез келген үйде атылған оқ басқа барлық үйлерде естіледі. Королева Жозефина Патшалықта кем дегенде бір адал емес ер адамның табылғанын және күйеуінің адал емес екенін білетін әйел, оның адал еместігін білген күнінен кейін келесі түнде оны атуға тиіс екенін жариялады. Әйелдер бұл жағдайды қалай шешті?
Шешім
Жозефинаның проблемасы – жалпы жағдайдың тағы бір жақсы мысалы. Егер тек 1 адал болмаған күйеу болса, Патшалықтағы әрбір әйел мұны біледі, тек оның әйелі ғана барлығының адал екеніне сенеді. Осылайша, ол патшайымнан адал емес еркектердің бар екенін естіген кезде, өзінің күйеуінің адал емес екенін біліп, оны атып өлтіреді. Егер 2 адал болмаған күйеу болса, олардың екі әйелі де тек 1 адал емес күйеу бар деп сенеді (екіншісі). Сондықтан олар жоғарыда айтылған жағдайдың орын алуын күтеді, яғни екінші күйеудің әйелі оны келесі күні түнгі жарты сағатта атып өлтіреді деп күтеді. Егер оқ атылса, олар жоғарыда аталған жағдайдың орын алмағанын түсінеді, демек, 1-ден астам адал емес күйеу болуы керек, және (басқаларының барлығы адал екенін білгендіктен) қосымшасы – олардың өзінің күйеуі. Егер 3 адал болмаған күйеу болса, олардың әрқайсысының әйелі тек 2 күйеудің адал емес екеніне сенеді, сондықтан олар жоғарыда айтылған жағдайды қолданып, екі күйеудің де екінші күні атып өлтіріледі деп күтеді. Егер оқ атылмаса, олар жоғарыда аталған жағдайдың орын алмағанын түсінеді, демек, екіден астам адал емес күйеу болуы керек, және бұрынғыдай, олардың өзінің күйеуі қосымша болу үшін жалғыз үміткер. Жалпы, егер n адал емес күйеу болса, олардың әрқайсысының әйелдері n-1 деп сенеді және n-1-ші күні түнгі жарты сағатта оқ атылатынын күтеді. Егер оқ атылмаса, олар өзінің күйеуінің n-ші адал емес күйеу екенін біледі. Бұл проблеманы «Адалдығын сақтай алмаған күйеулердің проблемасы», «Адал емес әйелдердің проблемасы», «Лайлы балалардың проблемасы» деп те атайды. Бұл «Көк көздердің проблемасына» логикалық тұрғыдан толық сәйкес келеді. Бұл мәселе сонымен қатар C. L. Людің «Дискретті математика элементтері» атты классикалық оқулығында қара және ақ шляпаларға қатысты мәселе ретінде де кездеседі.
Сипаттама
Логикашылардың құпия жиналысында Бас Логик әрбір қатысушының басына бір лента тақты, оны басқалар көре алады, бірақ әрбір адам өзі көре алмайды. Ленталардың көптеген түрлі түстері болды. Логикашылар шеңберге отырды, ал Бас Логик оларға орманнан белгілі бір уақыт аралығымен қоңырау соғылатынын хабарлады: логикашы өз маңдайындағы лентаның түсін білгенде, келесі қоңырау соққанда шығып кетуі керек. Оларға сөйлеуге, айна немесе камера қолдануға, немесе лентаның түсін анықтау үшін логикадан басқа әдіс қолдануға тыйым салынды. Егер жиналысқа жасанды адамдар кірсе, уақытында шықпағандар қатаң түрде уақытында шығарылады. Сол сияқты, ертерек шығуға тырысқандар күштеп ұсталып, дұрыс уақытта шығарылады. Бас Логик жиналғандарды жұмбақтың кез келген нағыз логикашы үшін шешілмейтін емес екеніне сендірді. Олар қалай шешті?
Шешім
Алиса логиктер конвенциясында – жалпы индукция және логикалық секіріс. Логикалық секіріс: Әрбір түс шеңбер бойында кем дегенде екі рет кездесуі керек. Өйткені, Ұстаз бұл жұмбақты кез келген логик шеше алмайтындай емес деп мәлімдеген. Егер қандай да бір түс шеңберде бір рет ғана болса, сол түсті таққан логик оның проблемада бар екенін қалай білуі мүмкін, және жауап беруге шамасы келмейді. Әр логик шеңбер бойындағы әр түстің қанша рет кездесетінін санауға болады. Егер сіз логик болсаңыз және басқа түсті бір рет ғана көрсеңіз, әр түс кем дегенде екі рет болуы керек екенін білгендіктен, жалғыз түстің себебі – сіздің өзіңіздің жолағыңыздың түсі. Осы себепті, мұндай жалғыз түс тек біреу ғана болуы мүмкін, сондықтан сіз бірінші қоңыраумен кете аласыз. Сол сияқты, басқа түсті бір рет көрген логиктер өздерінің түсін анықтай алады және қадір-қасиетпен кетеді немесе жасырын кіргендер ретінде сыртқа шығарылады. Басқаша айтқанда, егер қандай да бір түстің тек екі жолағы болса, ол бірінші қоңырау соққаннан кейін алынып тасталады. Содан кейін қалған әр түстің кем дегенде үш жолағы болуы керек. Егер сіз қандай да бір түсті бір рет те көрмесеңіз, бірақ бір түсті екі рет көрсеңіз, егер осы түстің тек осы екі жолағы ғана болса, онда осы екі логик бірінші қоңыраумен кетуі керек еді. Олар кетпегендіктен, сіздің жолағыңыз да сол түстің болуы мүмкін, сондықтан сіз екінші қоңыраумен кете аласыз. Сондықтан, әр логик күтеді, олардың күткен түсіндегі топ кетпегенше. Содан кейін олар олардың сол түсті таққанын біледі және келесі қоңыраумен кетеді. Қалғанда тек бір түс болғанда, олардың бәрі келесі қоңыраумен кетеді, өйткені олар басқа түс болуы мүмкін емес екенін біледі (әйтпесе олар өздерінің түсін қалай білуі мүмкін).
Сипаттама
Бірнеше ойыншының әрқайсысы бас киім киеді, ол әртүрлі белгіленген түстерде болуы мүмкін. Ойыншылар кем дегенде кейбір басқа ойыншылардың бас киімдерінің түсін көре алады, бірақ өздерінікіні емес. Байланыс өте шектеулі немесе мүлдем болмаған жағдайда, кейбір ойыншылар өз бас киімдерінің түсін болжауы керек. Мәселе – ойыншылардың өздері көрген бас киімдерге және басқа ойыншылардың іс-әрекеттеріне сүйене отырып, бас киімдерінің түсін анықтауға арналған стратегияны табуда. Кейбір нұсқаларда олар дұрыс болжау үшін бірінші болуға тырысады; ал басқаларында олар дұрыс болжау мүмкіндігін барынша арттыру үшін алдын ала стратегия жасай алады. Бір нұсқасы Тодд Эберттің 1998 жылғы Калифорния университетінде (Санта-Барбара) докторлық диссертациясының нәтижесінде жаңалыққа ие болды. Бұл алгебралық кодтау теориясымен байланысты кооперативтік ойынға қатысты стратегиялық сұрақ. Үш ойыншыға олардың әрқайсысына қызыл немесе көк бас киім беріледі. Олар бір-біріне қарама-қарсы тұрғанда, егер басқа ойыншының басында қызыл бас киімді көрсе, қол көтерулері керек. Шапанының түсін дұрыс тауып алған бірінші ойыншы жеңіске жетеді. Үш ойыншының барлығы қол көтереді. Ойыншылар бірнеше минут бойы болжамай тұрғаннан кейін, бір ойыншы "Қызыл" деп жариялайды және жеңіп шығады. Жеңімпаз қалай жеңді және әркімнің бас киімінің түсі қандай?
Шешім
Біріншіден, егер екі адамның бас киімдері көк болса, барлығы қол көтермес еді. Келесісі, егер 1-ші ойыншы 2-ші ойыншының басында көк бас киім, ал 3-ші ойыншының басында қызыл бас киім көрсе, онда 1-ші ойыншы өзінің бас киімі қызыл болуы керек екенін бірден білер еді. Осылайша, көк бас киім көрген кез келген ойыншы бірден дұрыс жауап бере алады. Соңында жеңімпаз ешкім бірден жауап бермейтінін түсінеді, демек, көк бас киімдер жоқ, сондықтан барлық бас киімдер қызыл болуы керек. Егер әрбір ойыншы жауап беруге міндетті болса, бірақ жауап беру уақытын өзі таңдай алса, барлық ойыншылардың дұрыс жауап беруіне мүмкіндік беретін ынтымақтастық стратегиясы бар, тек барлық бас киімдер бір түсті болмаса ғана. Әр ойыншы келесідей әрекет етуі керек: сіз көретін көк бас киімдердің b және қызыл бас киімдердің r санын санаңыз. Ең ертерек – «b» секунд немесе «r» секунд күтіңіз. Егер ешкім сөйлемесе, егер көк бас киімдер қызыл бас киімдерге қарағанда аз болса, сіздің бас киіміңіз көк, ал қызыл бас киімдер көк бас киімдерге қарағанда аз болса, сіздің бас киіміңіз қызыл деп жауап беріңіз. Егер сіз әлі жауап бермеген болсаңыз, сіздің бас киіміңіз алғаш сөйлегендердің біреуінің бас киіміне қарама-қарсы түсті деп жауап беріңіз. Жалпы, B көк бас киім және R қызыл бас киім бар деп есептейік. Үш жағдай бар. Егер B = R болса, көк бас киім киген ойыншылар B-1 көк бас киім және R қызыл бас киім көреді, сондықтан B-1 секунд күтіп, содан кейін өзінің бас киімі көк екенін дұрыс жауап беріңіз. Сол сияқты, қызыл бас киім киген ойыншылар қызыл бас киім киіп отырғанын дұрыс жауап беру үшін R-1 секунд күтеді. Осылайша, барлық ойыншылар бір уақытта дұрыс жауап береді. Егер B < R болса, көк бас киім кигендер B-1 көк бас киім және R қызыл бас киім көреді, ал қызыл бас киім кигендер B көк бас киім және R-1 қызыл бас киім көреді. B-1 < B ≤ R-1 болғандықтан, көк бас киім киген ойыншылар бірінші болып жауап береді, өзінің бас киімі көк екенін дұрыс жауаптайды. Содан кейін басқа ойыншылар өзінің бас киімі қызыл екенін дұрыс жауаптайды. R < B жағдайы да осыған ұқсас.
Count the numbers b of blue hats and r of red hats that you see. Wait b seconds or r seconds, whichever is sooner. If nobody has yet spoken, guess that your hat is blue if you can see fewer blue hats than red hats, or red if you can see fewer red hats than blue hats. If you have not yet spoken, guess that your hat is of the opposite colour to that of one of the first people to speak. Suppose that in total there are B blue hats and R red hats. There are three cases. If B = R then those players wearing blue hats see B−1 blue hats and B red hats, so wait B−1 seconds then correctly guess that they are wearing a blue hat. Similarly, those players wearing a red hat will wait R−1 seconds before guessing correctly that they are wearing a red hat. So all players make a correct guess at the same time. If B < R then those wearing a blue hat will see B−1 blue hats and R red hats, whilst those wearing a red hat will see B blue hats and R−1 red hats. Since B−1 < B ≤ R−1, those players wearing a blue hat will be the first to speak, guessing correctly that their hat is blue. The other players then guess correctly that their hat is red. The case where R < B is similar.
Сипаттама
Әңгіме бойынша, қылмыс жасағаны үшін төрт тұтқын тұтқындалады, бірақ түрме толып, күзетшінің оларды қоятын жері жоқ. Ақырында ол оларға бір жұмбақ беріп шешеді, егер олар сәтті болса, босатылады, ал егер сәтсіз болса, өлім жазасынан өтеді. Күзетші үш адамды қатар отырғызады. А қабырғаға қарап отырады, В – А-ға, ал С – В мен А-ға қарап отырады. Төртінші адамды экранның артына (немесе бөлек бөлмеге) жасырады. Күзетші төрт тұтқынға да шапан жабады. Ол екі қызыл және екі көк шапан бар екенін, әр тұтқын бір шапан кигенін, және әр тұтқын тек алдындағы шапанды ғана көретінін, бірақ өзінің немесе артындағы шапанды көре алмайтынын түсіндіреді. Экран артындағы төртінші адам ешкімді көре алмайды және оны ешкім көре алмайды. Тұтқындардың бірімен-бірі сөйлесуіне рұқсат жоқ. Егер тұтқынның біреуі өз басындағы шапанның қандай түсті екенін 100% нақтылықпен (болжаусыз) анықтай алса, оны жариялауы керек, сонда төрт тұтқынның бәрі босатылады. Егер тұтқын дұрыс емес жауап берсе, төрт тұтқынның бәрі өлім жазасына кесіледі. Жұмбақтың шешімі – тұтқындардың қалай құтылуы.
Шешім
Тұтқындар әр түстің тек екі шапаны бар екенін біледі. Егер С, А мен В-нің шапандарының түсі бірдей екенін көрсе, өзінің шапанының түсі одан өзгеше екенін түсінеді. Бірақ, егер А мен В-нің шапандарының түсі әртүрлі болса, С ештеңе айта алмайды. Маңыздысы, тұтқын В, белгілі бір уақыт күтіп, С не істейтінін білгеннен кейін, егер С ештеңе айтпаса, А мен В-нің шапандары әртүрлі болуы керек екенін түсінеді. А-ның шапанын көріп, ол өзінің шапанының түсін анықтай алады. Мұндай көптеген жұмбақтардағыдай, шешім барлық қатысушылардың толыққанды түрде рационалды және қажетті қорытындыларды жасауға жеткілікті интеллектуалдық қабілетке ие деген болжамға негізделген. Бұл жұмбақты шешкеннен кейін, тұтқын С-нің мағыналы үнсіздігі "Ақпарат алмасуға тыйым салу" ережесін бұза ма деп ойлану арқылы коммуникацияның мәніне қатысты түсініктерге қол жеткізуге болады (коммуникация әдетте "ақпаратты жеткізу" деп түсіндіріледі).
Сипаттама
Бұл нұсқада 3 тұтқын және 3 бас киім бар. Әр тұтқынға кездейсоқ түрде қызыл немесе көк түсті бас киім тағайындалады. Әрбір адам басқа екі адамның бас киімін көре алады, бірақ өзінікіні көре алмайды. Белгі берілген кезде, олардың әрқайсысы өзінің бас киімінің түсін атайды немесе жауап бермейді. Егер кем дегенде бір адам дұрыс атайтын болса және ешкім қате айтпаса, олар бостандыққа шығады (жауап бермеу дұрыс та, қате де емес).
Шешім
Бұл жұмбақтың 100% жеңіске жетектейтін стратегиясы жоқ, бірақ 75% мүмкіндікпен жеңуге болады. Топтың бас киімдерінің түстерін биттер ретінде қарастырсақ, бұл мәселені кодтау теориясының көмегімен, мысалы, Хэмминг кодтарын пайдаланып шешуге болады.
Сипаттама
Бұл жұмбақтың бір түрінде тұтқындар екі қара және екі ақ түсті шапан бар екенін біледі, сондай-ақ А мен В арасында қабырға орналасқан, бірақ В, С және Д тұтқындары өз алдарында кім тұрғанын көре алады, яғни Д – В, С және қабырғаны, В – қабырғаны, ал С – В және қабырғаны көреді. (А қайтадан көрінбейді және тек қара шапанның біреуін кию үшін ғана қатысады.) Олар бір-бірімен байланысқа түспей, барлығының шапандарының түсін қалай анықтай алады?
Шешім
Екі жағдай бар: ең қарапайым жағдайда төрт тұтқынның екеуі қара түсті бас киімдер киеді. Қалған екі тұтқынның әрқайсысы бір тұтқынның өзге түсті бас киім кигенін көреді. Ал күрделі жағдайда төрт тұтқынның екеуі бір түсті бас киімдер киеді, сонда А мен С қара түсті бас киімдер киеді. Біраз уақыттан соң, барлық төрт тұтқын да Д мен Б өз бас киімдерінің түсін анықтай алмағандықтан, А мен С қара түсті бас киімдер киіп отырғанын түсіне алады.
Сипаттама
Басқа нұсқада үш тұтқын және белгілі түстердегі бес шапан (мысалы, екі қара және үш ақ) қатысады. Үш тұтқынға тізіліп тұруға бұйырылады, А алдында, ал С артта тұрады. Оларға екі қара және үш ақ шапан болатыны айтылады. Содан кейін әр тұтқынның басына бір шапан кигізіледі; әр тұтқын тек алдында тұрғандардың шапанын ғана көреді, өзінікіні емес. Шапанының түсін бірінші дұрыс атай алатын тұтқын босатылады. Тұтқындардың арасында ешқандай байланысқа рұқсат етілмейді.
Сипаттама
Бұл нұсқада 10 тұтқын және 10 бас киім бар. Әр тұтқынға кездейсоқ түрде қызыл немесе көк түсті бас киім тағайындалады, бірақ бас киімдердің әр түсінен қанша бар екенін тұтқындар білмейді. Тұтқындар бір қатарға тізіледі, мұнда әрқайсысы алдындағы тұтқынның бас киімін көре алады, бірақ артқысын көре алмайды. Кезектің соңғы тұтқынынан бастап алға қарай жылжып, олардың әрқайсысы тек бір сөз айтуы керек, ол "қызыл" немесе "көк" болуы тиіс. Егер айтқан сөз олардың бас киімінің түсімен сәйкес келсе, оларды босатады, әйтпесе сол жерде өлтіреді. Мейірімді қарауыл бір сағат бұрын оларды осы сынақ туралы ескертеді және оларға белгіленген ережелерді сақтау арқылы 10 тұтқынның 9-ы міндетті түрде аман қалады, ал 1-інің аман қалу мүмкіндігі 50/50 дейді. Мақсатқа жету жоспары қандай?
Шешім
Тұтқындар егер бірінші тұтқын қызыл шапқыштардың тақ санын көрсе, "қызыл" деп айласуға келіседі. Осылайша, қалған тоғыз тұтқын өз шапқыларының түсін, артындағы тұтқын жауап бергеннен кейін біле алады.
Сипаттама
Бұрынғыдай, 10 тұтқын және 10 бас киім бар. Әр тұтқынға кездейсоқ түрде қызыл немесе көк түсті бас киім тағайындалады, бірақ бас киімдердің әр түсінен нешеу бар екенін тұтқындар білмейді. Тұтқындар бөлмеде басқалардың бас киімдерін көре алатындай, бірақ өздерінікіні көре алмайтындай етіп орналастырылады. Енді олардың әрқайсысы бір уақытта тек бір сөз айтуы керек, ол "қызыл" немесе "көк" болуы тиіс. Егер айтқан сөздері бас киімдерінің түсімен сәйкес келсе, босатылады, ал егер жеткілікті тұтқындар бостандыққа шығар болса, қалғандарын құтқара алады. Мейірімді қарауыл бір сағат бұрын оларды осы сынақ туралы ескертеді. Егер олар белгіленген ережелерге сәйкес жоспар құра алса, 10 тұтқынның 5-еуі міндетті түрде босатылып, қалғандарын құтқаруға мүмкіндік алады. Мақсатқа жету үшін қандай жоспар керек?
Шешім
Тұтқындар жұп болып тұрады. Тұтқындардың бір жұбында (А, В) А, В-нің басында көретін түсін айтады, ал В, А-ның басында көретін қарама-қарсы түсті айтады. Егер екеуі де бірдей түсті бас киім кисе, А босатылады (ал В босатылмайды), егер түстер әртүрлі болса, В босатылады (ал А босатылмайды). Барлығы 5 тұтқын дұрыс жауап берді, ал 5 тұтқын дұрыс жауап бермеді. Бұл жұптың кім А және кім В екенін біле алатынын болжайды, бірақ мұндайға рұқсат етілмеуі мүмкін. Басқаша айтқанда, тұтқындар екі топқа бөлініп, әр топта 5 адамнан тұрады. Бір топ қызыл бас киімдердің саны жұп екенін болжайды, ал екінші топ – тақ екенін болжайды. Есту мүмкіндігі бар нұсқаға ұқсас, олар осы болжамнан өз бас киімдерінің түсін анықтай алады. Дәл бір топ дұрыс болжайды, яғни 5 тұтқын дұрыс жауап береді, ал 5 тұтқын дұрыс жауап бермейді. Ескеріңіз, тұтқындар 5 тұтқыннан артық босатылуына кепілдік беретін стратегияны таба алмайды. Шындығында, бір тұтқын үшін, дұрыс жауап берген жағдайлар, дұрыс жауап бермеген жағдайлармен бірдей. Сондықтан, 6 немесе одан да көп тұтқын дұрыс жауап берген бас киімдердің түстерінің саны, 4 немесе одан аз тұтқын дұрыс жауап бергеннен көп.
Сипаттама
Бұл нұсқада, санауға болатын шексіз тұтқын, әрқайсысының басына кездейсоқ түрде қызыл немесе көк түсті шапка кигізілген, бір қатарға тұзады. Әр тұтқын қатардың басына қарай жүзі бұрылып тұрады, сондықтан алдындағы барлық шапканы көреді, бірақ артындағы шапканы көре алмайды. Қатардың басынан бастап, әр тұтқын өзінің шапкасының түсін дұрыс атауы керек, әйтпесе сол жерде өлтіріледі. Бұрынғысын сияқты, тұтқындар алдын ала келісе алады, бірақ бұл жолы қатарға тұрғаннан кейін ешбір тұтқын екінші тұтқынның айтқанын ести алмайды. Сұрақ мынада: тек шектеулі ғана тұтқынның өлтірілуін қамтамасыз етуге бола ма?
Шешім
Егер таңдау аксиомасын қабылдасақ және тұтқындардың әрқайсысының (реалистік емес) санаусыз шексіз ақпарат көлемін жаттауға және санаусыз шексіз есептеу күрделілігі бар есептеулерді орындауға қабілеті бар деп есептесек, жауап – иә. Шын мәнінде, егер біз түстердің санаусыз көп түрін және тұтқындардың санаусыз көп санын рұқсат етсек те, таңдау аксиомасы, әрбір тұтқын басқа тұтқындардың бас киімдерін (тек алдындағылар емес) немесе кем дегенде басқа тұтқындардың бас киімдерінің шекті санынан басқа барлығын көруге мүмкіндік беретін жағдайда, тек шекті саны ғана тұтқындардың өлуіне кепілдік беретін шешім ұсынады. Екі түстің жағдайындағы шешім келесідей, ал санаусыз шексіз түстің жағдайындағы шешім негізінен бірдей: қатар тұрған тұтқындар 0 және 1 тізбегін құрайды, мұнда 0 көк түсті, ал 1 қызыл түсті білдіреді. Тізбекке орналастырылғанға дейін тұтқындар келесі эквиваленттілік қатынасын анықтайды: екі тізбек шекті сандағы элементтерден кейін бірдей болса, олар эквивалентті болады. Осы эквиваленттілік қатынасынан тұтқындар эквиваленттілік сыныптарының жиынтығын алады. Таңдау аксиомасын қабылдасақ, әрбір эквиваленттілік сыныбынан бір өкілдік тізбектер жиынтығы бар. (Барлық нақты мәндерді есептеу мүмкін емес, бірақ таңдау аксиомасы мәндердің белгілі бір жиынтығы бар екенін білдіреді, сондықтан тұтқындардың оракулға қол жеткізілімі бар деп есептейміз.) Олар өз кезегіне орналасқанда, әрбір тұтқын шекті сандағы бас киімдерден басқа барлығын көре алады, сондықтан бас киімдердің нақты тізбегі қай эквиваленттілік сыныбына жататынын көре алады. (Бұл әрбір тұтқынға сәйкес келу үшін санаусыз көп салыстырулар жасауға болады деп болжайды, әр сыныпты салыстыру үшін санаусыз көп жеке бас киімдерді салыстыру қажет.) Содан кейін олар тиісті эквиваленттілік сыныбынан алынған өкілдік тізбекте болғандай, бас киімдерінің түсін болжай бастайды. Нақты тізбек пен өкілдік тізбек бірдей эквиваленттілік сыныбында болғандықтан, олардың элементтері белгілі бір N тұтқын санынан кейін бірдей болады. Осы N тұтқыннан кейінгі барлық тұтқындар құтқарылады. Тұтқындар өз бас киімдерінің түсі туралы ақпаратқа ие емес және қандай түс болса да бірдей болжайды, сондықтан әр тұтқынның өлтірілу ықтималдығы 50% құрайды. Көптеген тұтқындардың өлтірілу ықтималдығы бар болғанымен, тек шекті саны ғана өлтіріледі деген парадоксқа ұшырағандай көрінуі мүмкін. Бұл парадоксқа шешім – тұтқындардың әрқайсысының болжамын анықтау үшін қолданылатын функция өлшенетін функция емес. Мұны түсіну үшін, 0 тұтқынның өлтірілу жағдайын қарастырайық. Бұл жағдай тек және ғана нақты тізбек таңдалған өкілдік тізбектердің бірі болса ғана орын алады. Егер 0 және 1 тізбектерін 0 мен 1 арасындағы нақты санның екілік өрнегі ретінде қарастырсақ, онда өкілдік тізбектер өлшенбейтін жиынды құрайды. (Бұл жиын Vitali жиынына ұқсас, тек бір ғана айырмашылығы – эквиваленттілік сыныптары барлық рационалды сандарға қарағанда біртұтас екілік өрнегі бар сандарға қатысты құрылады.) Сондықтан 0 тұтқынның өлтірілуіне ешқандай ықтималдық тағайындауға болмайды. Аргумент басқа да шекті саны бар тұтқындар үшін де бірдей, әр өкілдің шекті санымен сәйкес келеді.
The prisoners standing in line form a sequence of 0s and 1s, where 0 is taken to represent blue, and 1 is taken to represent red. Before they are put into the line, the prisoners define the following equivalence relation over all possible sequences that they might be put into: Two sequences are equivalent if they are identical after a finite number of entries. From this equivalence relation, the prisoners get a collection of equivalence classes. Assuming the axiom of choice, there exists a set of representative sequences—one from each equivalence class. (Almost every specific value is impossible to compute, but the axiom of choice implies that some set of values exists, so we assume that the prisoners have access to an oracle.) When they are put into their line, each prisoner can see all but a finite number of hats, and can therefore see which equivalence class the actual sequence of hats belongs to. (This assumes that each prisoner can perform an uncountably infinite number of comparisons to find a match, with each class comparison requiring a countably infinite number of individual hat comparisons). They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class. Because the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after some finite number N of prisoners. All prisoners after these first N prisoners are saved. Because the prisoners have no information about the color of their own hat and would make the same guess whichever color it has, each prisoner has a 50% chance of being killed. It may seem paradoxical that an infinite number of prisoners each have an even chance of being killed and yet it is certain that only a finite number are killed. The solution to this paradox lies in the fact that the function employed to determine each prisoner's guess is not Measurable function. To see this, consider the case of zero prisoners being killed. This happens if and only if the actual sequence is one of the selected representative sequences. If the sequences of 0s and 1s are viewed as binary representations of a real number between 0 and 1, the representative sequences form a non measurable set. (This set is similar to a Vitali set, the only difference being that equivalence classes are formed with respect to numbers with finite binary representations rather than all rational numbers.) Hence no probability can be assigned to the event of zero prisoners being killed. The argument is similar for other finite numbers of prisoners being killed, corresponding to a finite number of variations of each representative.
Сипаттама
Бұл нұсқа бұрынғысына ұқсас, бірақ тұтқындар басқа тұтқындардың айтқан түстерін ести алады. Сұрақ мынада: ең нашар жағдайда тұтқындардың ең азы қалай өлуі үшін олардың оптималды стратегиясы қандай болуы керек?
Шешім
Егер тұтқындарға басқа тұтқындар айтқан түстерді естіруге мүмкіндік берілсе, біріншісінен басқа барлық тұтқындардың өмірін сақтап қалуға болады, ал ол 50% ықтималдықпен өледі. Мұны істеу үшін жоғарыда көрсетілгендей эквиваленттілік қатынасын анықтаймыз және әр эквиваленттілік класынан қайтадан өкілдік тізбекті таңдаймыз. Енді әр кластағы әрбір тізбекті 0 немесе 1 деп белгілейміз. Бірінші кезекте, өкілдік тізбекті 0 деп белгілейміз. Содан кейін, өкілдік тізбектен жұп сандардағы орындармен ерекшеленетін кез келген тізбекті 0 деп, ал тақ сандардағы орындармен ерекшеленетін кез келген тізбекті 1 деп белгілейміз. Осылайша, біз әр мүмкін шексіз тізбекті 0 немесе 1 деп белгіледік, мұнда маңызды қасиет – тек бір санмен ғана ерекшеленетін кез келген екі тізбектің қарама-қарсы белгілері болады. Алғашқы адамнан түстерді немесе, жаңа түсіндіруде, 0 немесе 1 деп айтуды сұрағанда, ол тек көріп отырған тізбектің белгісін айтады. Осы ақпаратты естігеннен кейін, одан кейінгі әркім өзінің бас киімінің түсін нақты анықтай алады. Екінші адам бірінші адам көріп отырған тізбектің бірінші цифрынан басқа барлық цифрларын көреді. Демек, оның білуінше, бірінші адам белгілей алатын екі мүмкін тізбек бар: біреуі 0-ден басталады, екіншісі 1-ден басталады. Біздің белгілеу схемамызға сәйкес, бұл екі тізбекке қарама-қарсы белгілер беріледі, сондықтан бірінші адамның айтқанына сүйене отырып, екінші адам бірінші адамның көрген екі мүмкін тізбектің қайсысы екенін анықтай алады, соның арқасында ол өзінің бас киімінің түсін анықтай алады. Сол сияқты, тізімдегі келесі әр адам өзінің бас киімінің түсіне сәйкес келетіннен басқа тізбектің барлық цифрларын біледі. Ол өзінің алдындағыларды біледі, өйткені олар айтылды, ал өзінен кейінгілерді көре алады. Осы ақпаратты пайдаланып, ол бірінші адам айтқан белгіні өзінің бас киімінің түсін анықтау үшін қолдана алады. Осылайша, бірінші адамнан басқа барлық адамдар әрқашан дұрыс жауап береді.
Сипаттама
Эберттің мәселені қоюынша, болжауға кірісетін барлық ойыншылар бірдей, алдын ала белгіленген уақытта болжауы керек, бірақ барлық ойыншылардың міндетті түрде болжауы қажет емес. Барлық ойыншылар дұрыс болжай алмайтындықтан, ойыншылар жеңеді, егер кем дегенде бір ойыншы болжаса және болжағандардың барлығы да дұрыс болжаса. Ойыншылар жеңіске жету мүмкіндігін қалай барынша арттыра алады?