Puzzle indukcyjne - Induction puzzles

Część serii na
Puzzle
Kawałek układanki
Rodzaje
Zgadywanie
Logika
Mechaniczny
Słowo i liczba
Puzzle gry wideo
Metapuzzle
Tematy
Listy

Puzzli indukcyjne są łamigłówki logiczne , które są przykładami wieloagentowego rozumowania , w którym roztwór ewoluuje wraz z zasadą indukcji .

Scenariusz łamigłówki zawsze obejmuje wielu graczy o tej samej zdolności rozumowania, którzy przechodzą przez te same etapy rozumowania. Zgodnie z zasadą indukcji rozwiązanie najprostszego przypadku czyni oczywistym rozwiązanie kolejnego skomplikowanego przypadku. Po rozwiązaniu najprostszego przypadku łamigłówki indukcyjnej cała łamigłówka jest rozwiązywana później.

Typowe cechy charakterystyczne tych łamigłówek obejmują każdą łamigłówkę, w której każdy uczestnik ma określoną informację o wszystkich innych uczestnikach, ale nie o sobie. Ponadto, zwykle podaje się jakąś wskazówkę, aby zasugerować, że uczestnicy mogą ufać sobie nawzajem — są zdolni do teorii umysłu .

Zabłocone puzzle dla dzieci to najczęściej pojawiająca się zagadka indukcyjna w literaturze naukowej dotyczącej logiki epistemicznej . W lutym 2020 r. 437 wejść na Google naukowiec wspomniał o zabłoconej układance dla dzieci. Zabłocone puzzle dla dzieci to wariant znanych mędrców lub zdradzających żon/mężów.

Łamigłówki z kapeluszami to indukcyjne odmiany puzzli, których historia sięga 1961 roku. W wielu wariantach zagadki z kapeluszami są opisywane w kontekście więźniów. W innych przypadkach zagadki z kapeluszami opisywane są w kontekście mędrców.

Zabłocone puzzle dla dzieci

Opis

Jest grupa uważnych dzieci. Myślą doskonale logicznie. Dzieci uważają, że można mieć zabłoconą twarz. Żadne z dzieci nie jest w stanie samodzielnie określić stanu swojej twarzy. Ale każde dziecko zna stan twarzy wszystkich innych dzieci. Opiekun mówi dzieciom, że przynajmniej jedno z nich ma zabłoconą twarz. Odtąd opiekun zaczyna liczyć, a po każdym udarze każde zabłocone dziecko ma możliwość wystąpienia do przodu.

Logiczne rozwiązanie

Załóżmy, że jest tylko dwoje dzieci: Alicja i Bob. Jeśli tylko Alice jest brudna, to przy pierwszym uderzeniu wystąpi do przodu, ponieważ nie widzi żadnych innych brudnych twarzy. To samo dotyczy Boba. Jeśli Alicja zobaczy, że Bob nie robi kroku do przodu przy pierwszym pociągnięciu, musi dojść do wniosku, że z pewnością widzi inne zabłocone dziecko i jednocześnie zrobi krok do przodu przy drugim pociągnięciu.

Załóżmy, że jest tylko troje dzieci: Alice, Bob i Charly. Jeśli jest mniej niż 3 zabłocone dzieci, układanka ewoluuje jak w przypadku 2 dzieci. Jeśli Charly widzi, że Alice i Bob są zabłoceni i nie robią kroku do przodu przy drugim uderzeniu, wszyscy razem zrobią krok do przodu przy trzecim.

Można udowodnić, że zabłocone dzieci po udarze wystąpią do przodu .

Rozwiązanie teorii gier

Przedstawienie Muddy Children Puzzle w obszernej formie..svg
Przedstawienie Muddy Children Puzzle dla dwóch graczy w rozbudowanej formie . Wstępny ruch z natury jest zabarwiony na zielono. Alicja jest w kolorze czerwonym, a Bob jest w kolorze niebieskim. Ta gra ma tylko jedną równowagę Nasha . Działania przewidywane przez tę równowagę mają kolor czarny.

Zabłocone puzzle dla dzieci można również rozwiązać za pomocą indukcji wstecznej z teorii gier . Zabłocone puzzle dla dzieci można przedstawić jako rozbudowaną grę z niedoskonałymi informacjami . Każdy gracz ma dwie akcje — cofnij się i wykonaj krok do przodu. Na początku gry występuje ruch z natury , który określa dzieci z zabłoconymi twarzami i bez nich. Dzieci nie komunikują się jak w grach niekooperacyjnych . Każde uderzenie to jednoczesny ruch dzieci. Jest to gra sekwencyjna o nieograniczonej długości. Rozwiązanie oparte na teorii gier wymaga dodatkowych założeń:

  1. Wszystkie dzieci są racjonalne, a racjonalność wszystkich dzieci jest powszechna . Oznacza to, że Alicja jest racjonalna, Alicja wie, że Bob jest racjonalny, a Alicja wie, że Bob wie, że Charly jest racjonalny i tak dalej i na odwrót.
  2. Wysunięcie się do przodu bez zabłoconej twarzy skutkuje dużą karą.
  3. Wystąpienie z zabłoconą twarzą skutkuje nagrodą.
  4. Każde uderzenie skutkuje niewielką ujemną karą, czyli współczynnikiem zniżkowym dla każdego dziecka, dopóki którekolwiek z nich nie wystąpi. Każda wielokrotność mniejszej kary jest zawsze mniejszym złem niż wielka kara.

Jeśli tylko Alice jest zabłocona, to ostatnie założenie sprawia, że ​​wahanie się jest dla niej irracjonalne. Jeśli Alice i Bob są zabłoceni, Alicja wie, że jedynym powodem pozostawania Boba po pierwszym uderzeniu jest obawa przed dużą karą przed zrobieniem kroku do przodu bez zabłoconej twarzy. W przypadku zabłoconych dzieci, czasy odebrania mniejszej kary są nadal lepsze niż duże kary.

Puzzle z kapeluszami króla mędrców

Opis

Król wezwał na swój dwór trzech najmądrzejszych ludzi w kraju, aby zdecydować, kto zostanie jego nowym doradcą. Nałożył im kapelusz na każdą głowę, tak aby każdy mędrzec mógł zobaczyć wszystkie inne kapelusze, ale żaden z nich nie mógł zobaczyć swoich. Każdy kapelusz był albo biały, albo niebieski. Król dał słowo mędrcom, że przynajmniej jeden z nich nosił niebieski kapelusz; innymi słowy, może być jeden, dwa lub trzy niebieskie kapelusze, ale nie zero. Król ogłosił również, że konkurs będzie sprawiedliwy dla wszystkich trzech mężczyzn. Mędrcom również zabroniono rozmawiać ze sobą. Król oświadczył, że ten, kto wstanie pierwszy i prawidłowo ogłosi kolor własnego kapelusza, zostanie jego nowym doradcą. Mędrcy siedzieli bardzo długo, zanim jeden wstał i poprawnie ogłosił odpowiedź. Co powiedział i jak to wypracował?

Rozwiązanie

Królowie Mędrcy to jedna z najprostszych zagadek indukcyjnych i jeden z najwyraźniejszych wskaźników zastosowanej metody.

  • Załóżmy, że był jeden niebieski kapelusz. Osoba nosząca ten kapelusz widziałaby dwa białe kapelusze, a ponieważ król określił, że istnieje przynajmniej jeden niebieski kapelusz, ten mądry człowiek natychmiast pozna kolor jego kapelusza. Jednak pozostali dwaj zobaczyliby jeden niebieski i jeden biały kapelusz i nie byliby w stanie od razu wywnioskować żadnych informacji ze swoich obserwacji. Dlatego ten scenariusz naruszyłby specyfikację króla, że ​​konkurs będzie sprawiedliwy dla każdego. Więc muszą być co najmniej dwa niebieskie kapelusze.
  • Załóżmy więc, że były to dwa niebieskie kapelusze. Każdy mądry człowiek w niebieskim kapeluszu widziałby jeden niebieski i jeden biały kapelusz. Zakładając, że już zdali sobie sprawę, że nie może być tylko jeden (przy użyciu poprzedniego scenariusza), wiedzieliby, że muszą być co najmniej dwa niebieskie kapelusze, a zatem od razu wiedzieliby, że każdy z nich nosi niebieski kapelusz. Jednak mężczyzna w białym kapeluszu zobaczyłby dwa niebieskie kapelusze i nie byłby w stanie od razu wywnioskować żadnych informacji ze swoich obserwacji. Ten scenariusz naruszałby zatem również specyfikację, zgodnie z którą konkurs byłby uczciwy dla każdego. Więc muszą być trzy niebieskie kapelusze.

Ponieważ muszą być trzy niebieskie kapelusze, pierwszy człowiek, który się domyśli, wstanie i powie niebieski.

Alternatywne rozwiązanie: Nie wymaga to zasady, aby konkurs był uczciwy dla każdego. Raczej opiera się na fakcie, że wszyscy są mądrymi ludźmi i że potrzeba trochę czasu, zanim dojdą do rozwiązania. Mogą być tylko 3 scenariusze, jeden niebieski kapelusz, dwa niebieskie kapelusze lub 3 niebieskie kapelusze. Gdyby był tylko jeden niebieski kapelusz, to noszący ten kapelusz widziałby dwa białe kapelusze i szybko wiedziałby, że musi mieć niebieski kapelusz, więc wstałby i od razu to ogłosił. Skoro tak się nie stało, to muszą być co najmniej dwa niebieskie kapelusze. Gdyby istniały dwa niebieskie kapelusze, wówczas którykolwiek z tych, który nosi niebieski kapelusz, spojrzałby w poprzek i zobaczyłby jeden niebieski kapelusz i jeden biały, ale nie znałby koloru własnego kapelusza. Gdyby pierwszy użytkownik niebieskiego kapelusza założył, że ma biały kapelusz, wiedziałby, że drugi użytkownik niebieskiego kapelusza zobaczy dwa białe kapelusze, a zatem drugi użytkownik niebieskiego kapelusza już wstałby i ogłosił, że miał na sobie niebieski kapelusz. Tak więc, ponieważ tak się nie stało, pierwszy użytkownik niebieskiego kapelusza wiedziałby, że nosi niebieski kapelusz, i mógłby wstać i ogłosić to. Ponieważ jeden lub dwa niebieskie kapelusze są tak łatwe do rozwiązania i nikt nie wstaje szybko, wszyscy muszą nosić niebieskie kapelusze.

Problem Józefiny

Opis

W Królestwie Józefiny każda kobieta musi zdać egzamin z logiki, zanim zostanie dopuszczona do małżeństwa. Każda zamężna kobieta wie o wierności każdego mężczyzny w Królestwie, z wyjątkiem własnego męża, a etykieta wymaga, aby żadnej kobiecie nie mówiono o wierności jej męża. Ponadto strzały wystrzały w dowolnym domu w Królestwie będą słyszane w każdym innym domu. Królowa Józefina ogłosiła, że ​​w Królestwie odkryto co najmniej jednego niewiernego mężczyznę i że każda kobieta, która wiedziała, że ​​jej mąż jest niewierny, musiała go zastrzelić o północy następnego dnia po tym, jak odkryła jego niewierność. Jak sobie z tym poradziły żony?

Rozwiązanie

Problem Josephine jest kolejnym dobrym przykładem ogólnego przypadku.

  • Jeśli jest tylko jeden niewierny mąż, to wie o tym każda kobieta w Królestwie, z wyjątkiem żony, która wierzy, że wszyscy są wierni. Tak więc, gdy tylko dowiaduje się od królowej, że istnieją niewierni mężczyźni, wie, że jej mąż musi być niewierny i zabija go.
  • Jeśli jest 2 niewiernych mężów, to obie ich żony uważają, że jest tylko 1 niewierny mąż (drugi). W ten sposób będą oczekiwać, że powyższy przypadek będzie miał zastosowanie i że żona drugiego męża zastrzeli go o północy następnego dnia. Kiedy nikt nie usłyszy wystrzału, zdadzą sobie sprawę, że powyższy przypadek nie miał zastosowania, więc musi być więcej niż 1 niewierny mąż, a (ponieważ wiedzą, że wszyscy inni są wierni), dodatkowy musi być ich własnym mężem.
  • Jeśli jest 3 niewiernych mężów, każda z ich żon uważa, że ​​jest ich tylko 2, więc będą oczekiwać, że powyższy przypadek będzie miał zastosowanie i obaj mężowie zostaną rozstrzelani drugiego dnia. Gdy nie usłyszą strzału, zorientują się, że powyższy przypadek nie miał zastosowania, więc musi być więcej niż 2 niewiernych mężów i tak jak wcześniej ich własny mąż jest jedynym kandydatem na dodatkowego.
  • Ogólnie rzecz biorąc, jeśli jest n niewiernych mężów, każda z ich żon będzie wierzyć, że jest n-1 i będzie oczekiwać, że usłyszy strzał o północy n-1 dnia. Kiedy tego nie robią, wiedzą, że ich własny mąż był n- tym.

Ten problem jest również znany jako problem niewiernych mężów, problem niewiernych żon, problem zabłoconych dzieci. Jest logicznie identyczny z Problemem Niebieskich Oczu .

Problem ten pojawia się również jako problem dotyczący czarnych i białych kapeluszy w klasycznym podręczniku CL Liu „Elementy matematyki dyskretnej”.

Alicja na zjeździe logików

Opis

Na tajnej konwencji logików mistrz logików umieścił opaskę na głowie każdego uczestnika, tak aby wszyscy inni mogli ją zobaczyć, ale sama osoba nie. Było wiele różnych kolorów opaski. Wszyscy logicy siedzieli w kręgu, a Mistrz poinstruował ich, że w lesie należy bić w regularnych odstępach czasu: w chwili, gdy logik pozna kolor własnego czoła, ma odejść przy następnym dzwonku. Poinstruowano ich, aby nie mówili, nie używali lustra lub aparatu fotograficznego lub w inny sposób unikali używania logiki w celu określenia koloru ich opaski. W przypadku wniknięcia na konwent oszustów, każdy, kto nie wyjdzie na czas, zostanie usunięty we właściwym czasie. Podobnie, każdy, kto próbowałby wyjść wcześniej, byłby szorstko przytrzymywany w miejscu i usuwany we właściwym czasie. Mistrz uspokoił grupę, stwierdzając, że zagadka nie będzie niemożliwa dla żadnego obecnego prawdziwego logika. Jak to zrobili?

Rozwiązanie

Alicja na zjeździe logików to ogólna indukcja plus skok logiki.

  • Skok logiki: Każdy kolor musi pojawić się co najmniej dwa razy wokół koła. Dzieje się tak, ponieważ Mistrz stwierdził, że żaden logik nie będzie w stanie rozwiązać zagadki. Gdyby jakiś kolor istniał tylko raz wokół koła, logik, który go nosił, nie miałby możliwości dowiedzenia się, że kolor istnieje w zadaniu, i nie byłoby możliwe, aby odpowiedzieli.
  • Każdy z logików może rozejrzeć się po okręgu i policzyć, ile razy widzi każdy kolor. Załóżmy, że jesteś jednym z logików i tylko raz widzisz inny kolor. Ponieważ wiesz, że każdy kolor musi istnieć co najmniej dwa razy wokół okręgu, jedynym wyjaśnieniem dla koloru singleton jest to, że jest to kolor twojego własnego paska. Z tego samego powodu może być tylko jeden taki singletonowy kolor, więc wyszedłbyś na pierwszym dzwonku.
  • Podobnie każdy Logicy, który zobaczy inny kolor tylko raz, powinien być w stanie określić swój własny kolor i albo odejdzie z godnością, albo zostanie wyrzucony jako infiltrator. Podobnie każdy kolor, dla którego są tylko dwa pasma tego koloru, zostanie wyeliminowany po pierwszym dzwonku. Następnie muszą być co najmniej trzy paski dowolnego pozostałego koloru.
  • Załóżmy, że nie widzisz żadnego koloru ani razu, ale kolor widzisz dwa razy. Gdyby to były jedyne opaski tego koloru, to ci dwaj logicy powinni byli wyjść przy pierwszym dzwonku. Skoro tak nie było, to może być tylko dlatego, że twoja własna opaska jest tego samego koloru, więc możesz wyjść przy drugim dzwonku.
  • Dlatego każdy logik obserwowałby, aż grupa danego koloru, którą spodziewał się odejść, nie odeszła. Wtedy wiedzieliby, że mają ten kolor i odejdą następnym dzwonkiem.
  • Gdy pozostał tylko jeden kolor, wszystkie one zniknęłyby na następnym dzwonku, ponieważ wiedzieliby, że nie mogą mieć innego koloru (odtąd nie mogliby poznać swojego koloru).

Podstawowa łamigłówka z kapeluszami

Opis

Kilku graczy nosi kapelusze, które mogą być w różnych określonych kolorach. Gracze widzą kolory przynajmniej niektórych czapek innych graczy, ale nie swoich. W przypadku bardzo ograniczonej komunikacji lub braku komunikacji, niektórzy gracze muszą odgadnąć kolor swojej czapki. Problem polega na znalezieniu strategii dla graczy, aby określić kolory ich czapek na podstawie czapek, które widzą i tego, co robią inni gracze. W niektórych wersjach konkurują o to, by jako pierwsi zgadli poprawnie; w innych potrafią wcześniej wypracować strategię współpracy i maksymalizacji prawdopodobieństwa poprawnych domysłów.

Jedna odmiana zyskała nowy rozgłos w wyniku doktoratu Todda Eberta w 1998 roku . praca dyplomowa na Uniwersytecie Kalifornijskim w Santa Barbara . Jest to pytanie strategiczne dotyczące gry kooperacyjnej , która ma powiązania z teorią kodowania algebraicznego .

Trzech graczy dowiaduje się, że każdy z nich otrzyma czerwoną lub niebieską czapkę. Muszą podnieść ręce, jeśli zobaczą czerwony kapelusz na innym graczu, gdy stoją w kręgu naprzeciwko siebie. Wygrywa ten, kto pierwszy odgadnie kolor swojego kapelusza.

Wszyscy trzej gracze podnoszą ręce. Po tym, jak gracze zobaczyli się przez kilka minut bez zgadywania, jeden z graczy ogłasza „Czerwony” i wygrywa. Jak to zrobił zwycięzca i jaki jest kolor kapeluszy wszystkich?

Rozwiązanie

Po pierwsze, gdyby dwoje ludzi miało niebieskie kapelusze, nie wszyscy podnieśliby rękę. Następnie, gdyby gracz 1 zobaczył niebieski kapelusz u gracza 2 i czerwony kapelusz u gracza 3, wówczas gracz 1 od razu wiedziałby, że jego własny kapelusz musi być czerwony. W ten sposób każdy gracz, który zobaczy niebieski kapelusz, może od razu zgadnąć. Ostatecznie zwycięzca uświadamia sobie, że skoro nikt od razu nie zgadnie, nie może być niebieskich kapeluszy, więc każdy kapelusz musi być czerwony.

W przypadku, gdy każdy gracz musi zgadywać, ale może swobodnie wybrać, kiedy zgadnąć, istnieje strategia współpracy, która pozwala każdemu graczowi zgadywać poprawnie, chyba że wszystkie kapelusze są tego samego koloru. Każdy gracz powinien postępować w następujący sposób:

  1. Policz liczby b niebieskich kapeluszy i r czerwonych kapeluszy, które widzisz.
  2. Odczekaj b sekund lub r sekund, w zależności od tego, co nastąpi wcześniej.
  3. Jeśli nikt jeszcze się nie odezwał, zgadnij, że twój kapelusz jest niebieski, jeśli widzisz mniej niebieskich czapek niż czerwonych, lub czerwony, jeśli widzisz mniej czerwonych czapek niż niebieskich.
  4. Jeśli jeszcze się nie odezwałeś, zgadnij, że twój kapelusz ma kolor przeciwny do koloru jednej z pierwszych osób, które się odezwały.

Załóżmy, że w sumie są czapki B niebieskie i czerwone czapki R. Są trzy przypadki.

Jeśli B = R, to gracze noszący niebieskie kapelusze widzą niebieskie kapelusze B-1 i B czerwone kapelusze, więc poczekaj B- 1 sekund, a następnie poprawnie zgadnij, że noszą niebieską czapkę. Podobnie, gracze noszący czerwoną czapkę odczekają R- 1 sekundy, zanim poprawnie zgadną, że noszą czerwoną czapkę. Tak więc wszyscy gracze dokonują poprawnego odgadnięcia w tym samym czasie.

Jeśli B < R, to ci, którzy noszą niebieskie kapelusze, zobaczą B- 1 niebieskie kapelusze i R czerwone kapelusze, podczas gdy ci, którzy noszą czerwone kapelusze, zobaczą B niebieskie kapelusze i R- 1 czerwone kapelusze. Ponieważ B -1 < B ≤ R -1, gracze noszący niebieską czapkę przemówią jako pierwsi, zgadując poprawnie, że ich czapka jest niebieska. Pozostali gracze odgadują, że ich kapelusz jest czerwony.

Przypadek, w którym R < B jest podobny.

Wariant z dwoma kapeluszami

Opis

Według opowieści czterech więźniów zostaje aresztowanych za przestępstwo , ale więzienie jest pełne, a dozorca nie ma ich gdzie umieścić. W końcu wymyśla rozwiązanie, dając im zagadkę, więc jeśli im się uda, mogą uciec, ale jeśli im się nie uda, zostaną straceni.

Dozorca sadza trzech mężczyzn w kolejce. B twarzą do ściany, C twarzą B, a D twarzą C i B. Czwarty mężczyzna, A, jest umieszczony za parawanem (lub w osobnym pomieszczeniu). Strażnik więzienny daje wszystkim czterem mężczyznom imprezowe kapelusze. Wyjaśnia, że ​​są dwa czarne kapelusze i dwa białe kapelusze, że każdy więzień nosi jedną z czapek i że każdy z więźniów widzi tylko kapelusze przed sobą, ale ani na sobie, ani za nim. Czwarty mężczyzna za parawanem nie widzi ani nie może być widziany przez żadnego innego więźnia. Zabroniona jest komunikacja między więźniami.

Jeśli jakiś więzień może dowiedzieć się, jaki kolor kapelusza ma na własnej głowie ze stuprocentową pewnością (bez zgadywania), musi to ogłosić, a wszyscy czterej więźniowie odejdą na wolność . Jeśli jakiś więzień zasugeruje nieprawidłową odpowiedź, wszyscy czterej więźniowie zostają straceni. Zagadką jest dowiedzieć się, jak więźniowie mogą uciec.

Rozwiązanie

Więźniowie wiedzą, że w każdym kolorze są tylko dwie czapki. Jeśli więc D zauważy, że B i C mają kapelusze w tym samym kolorze, D wywnioskuje, że jego własny kapelusz ma przeciwny kolor. Jeśli jednak B i C mają kapelusze w różnych kolorach, to D nie może nic powiedzieć. Kluczem jest to, że więzień C, po przejściu odpowiedniej przerwy i wiedząc, co zrobiłby D, może wywnioskować, że jeśli D nic nie mówi, czapki na B i C muszą być inne; w stanie zobaczyć kapelusz B, może wydedukować swój własny kolor kapelusza.

Podobnie jak w przypadku wielu tego typu łamigłówek, rozwiązanie opiera się na założeniu, że wszyscy uczestnicy są całkowicie racjonalni i wystarczająco inteligentni, aby dokonać odpowiednich dedukcji.

Po rozwiązaniu tej zagadki, pewien wgląd w naturę komunikacji można uzyskać, zastanawiając się, czy znaczące milczenie więźnia D narusza zasadę „braku komunikacji” (biorąc pod uwagę, że komunikacja jest zwykle definiowana jako „przekazywanie informacji”).

Wariant z trzema kapeluszami

Opis

W tym wariancie znajduje się 3 jeńców i 3 czapki. Każdy więzień otrzymuje losową czapkę, czerwoną lub niebieską. W sumie są trzy czerwone kapelusze i dwa niebieskie. Każda osoba widzi kapelusze dwóch innych, ale nie własne. Na zawołanie każdy z nich musi odgadnąć własny kolor kapelusza lub przejść. Wygrywają zwolnienie, jeśli przynajmniej jedna osoba odgadła poprawnie i żadna nie odgadła błędnie (podanie nie jest ani poprawne, ani błędne).

Ta łamigłówka nie ma 100% wygrywającej strategii, więc pytanie brzmi: Jaka jest najlepsza strategia? Która strategia ma największe prawdopodobieństwo wygranej?

Jeśli myślisz o kolorach kapeluszy jak o bitach, problem ten ma kilka ważnych zastosowań w teorii kodowania .

Rozwiązanie

Rozwiązanie i omówienie tej zagadki można znaleźć tutaj (również rozwiązanie analogicznej zagadki z siedmioma kapeluszami), a inne 3 warianty są dostępne na tej stronie łamigłówek logicznych (nazywają się one Mistrzami Logiki I-IV).

Wariant z czterema kapeluszami

Opis

W wariancie tej układanki więźniowie wiedzą, że są 3 czarne kapelusze i 1 biały kapelusz, a 3 więźniów może się widzieć, tj. D widzi B i C, B widzi D i C, a C widzi D i B. ( Znowu nie widać i jest tylko po to, by nosić ostatnią czapkę.) Jak mogą wywnioskować kolory wszystkich z nich bez komunikowania się?

Rozwiązanie

Są dwa przypadki: w trywialnym przypadku jeden z trzech więźniów nosi pojedynczy niekolorowy kapelusz. Każdy z pozostałych dwóch więźniów widzi, że jeden więzień ma na sobie odbarwioną czapkę. W nietrywialnym przypadku trzej więźniowie noszą kapelusze w tym samym kolorze, podczas gdy A nosi czapkę w innym kolorze. Po pewnym czasie wszyscy trzej więźniowie powinni być w stanie wywnioskować, że ponieważ żaden z pozostałych nie był w stanie określić koloru swojego kapelusza, A musi nosić niekolorowy kapelusz.

Wariant z pięcioma kapeluszami

Opis

W innym wariancie bierze udział tylko trzech więźniów i pięć kapeluszy o znanych kolorach (w tym przykładzie dwa czarne i trzy białe). Trzem więźniom nakazano stanąć w linii prostej przodem, z A z przodu i C z tyłu. Powiedziano im, że będą dwa czarne kapelusze i trzy białe kapelusze. Następnie na głowę każdego więźnia zakładany jest jeden kapelusz; każdy więzień widzi tylko kapelusze ludzi przed nim, a nie sam. Pierwszy więzień, który będzie w stanie poprawnie ogłosić kolor swojego kapelusza, zostanie zwolniony. Zabroniona jest komunikacja między więźniami.

Rozwiązanie

Załóżmy, że A nosi czarny kapelusz:

  • Jeśli B nosi również czarny kapelusz, C może natychmiast stwierdzić, że nosi biały kapelusz po spojrzeniu na dwa czarne kapelusze przed sobą.
  • Jeśli B nosi biały kapelusz, C nie będzie w stanie określić koloru swojego kapelusza (ponieważ jest czarny i biały). Tak więc B może szybko wywnioskować z czarnego kapelusza A i braku odpowiedzi C, że on (B) nosi biały kapelusz.

Więc jeśli A nosi czarny kapelusz, B lub C zareagują dość szybko.

Załóżmy, że A nosi biały kapelusz:

  • C nie widzi dwóch czarnych kapeluszy, więc nie jest w stanie określić koloru swojego kapelusza.
  • B widzi tylko biały kapelusz, więc nie może nic powiedzieć o swoim kapeluszu.

W tym przypadku A, B i C milczeliby przez jakiś czas, aż A ostatecznie wywnioskuje, że musi mieć biały kapelusz, ponieważ C i B milczeli przez pewien czas.

Jak wspomniano, w sumie są trzy białe kapelusze i dwa czarne kapelusze i trzej więźniowie o tym wiedzą. W tej zagadce możesz założyć, że wszyscy trzej więźniowie są bardzo sprytni i bardzo sprytni. Jeśli C nie mógł odgadnąć koloru swojego własnego kapelusza, to dlatego, że widział albo dwa białe kapelusze, albo po jednym w każdym kolorze. Gdyby zobaczył dwa czarne kapelusze, mógłby wywnioskować, że ma na sobie biały kapelusz.

Wariant z dziesięcioma kapeluszami

Opis

W tym wariancie jest 10 jeńców i 10 czapek. Każdy więzień otrzymuje losową czapkę, czerwoną lub niebieską, ale numer każdej kolorowej czapki nie jest znany więźniom. Więźniowie będą ustawieni w jednym szeregu, gdzie każdy widzi kapelusze przed sobą, ale nie z tyłu. Zaczynając od więźnia z tyłu linii i idąc do przodu, każdy z nich musi po kolei wypowiedzieć tylko jedno słowo, które musi być „czerwone” lub „niebieskie”. Jeśli słowo pasuje do koloru ich kapelusza, zostają uwolnieni, jeśli nie, zostają zabici na miejscu. Sympatyczny strażnik ostrzega ich o tym teście godzinę wcześniej i mówi im, że mogą sformułować plan, zgodnie z którym 9 z 10 więźniów na pewno przeżyje, a 1 ma 50/50 szans na przeżycie. Jaki jest plan osiągnięcia celu?

Rozwiązanie

Więźniowie zgadzają się, że jeśli pierwszy więzień zobaczy nieparzystą liczbę czerwonych kapeluszy, powie „czerwony”. W ten sposób dziewięciu pozostałych więźniów będzie znało swój własny kolor kapelusza po odpowiedzi więźnia za nimi.

Wariant z dziesięcioma kapeluszami bez słuchu

Opis

Tak jak poprzednio, jest 10 więźniów i 10 czapek. Każdy więzień otrzymuje losową czapkę, czerwoną lub niebieską, ale numer każdej kolorowej czapki nie jest znany więźniom. Więźniowie są rozmieszczeni w pomieszczeniu tak, aby widzieli kapelusze innych, ale nie własne. Teraz każdy z nich musi jednocześnie wypowiedzieć tylko jedno słowo, które musi być „czerwone” lub „niebieskie”. Jeśli słowo pasuje do koloru ich kapelusza, zostają uwolnieni, a jeśli wystarczająca liczba więźniów odzyska wolność, mogą uratować pozostałych. Sympatyczny strażnik ostrzega ich o tym teście godzinę wcześniej. Jeśli uda im się sformułować plan zgodnie z określonymi zasadami, 5 z 10 więźniów na pewno zostanie zwolnionych i będzie w stanie uratować pozostałych. Jaki jest plan osiągnięcia celu?

Rozwiązanie

Więźniowie łączą się w pary. W parze (A, B) więźniów A mówi kolor, który widzi na głowie B, który mówi przeciwny kolor, który widzi na głowie A. Następnie, jeśli oboje noszą kapelusze w tym samym kolorze, A jest zwolniony (a B nie), jeśli kolory są różne, B jest zwolniony (a A nie). W sumie 5 więźniów odpowiada poprawnie, a 5 nie. Zakłada to, że para może komunikować się, kto jest A, a kto B, co może być niedozwolone.

Ewentualnie więźniowie budują dwie grupy po 5 osób. Jedna grupa zakłada, że ​​liczba czerwonych kapeluszy jest parzysta, druga zakłada, że ​​liczba czerwonych kapeluszy jest nieparzysta. Podobnie jak wariant ze słuchem, mogą z tego założenia wywnioskować swój kolor kapelusza. Dokładnie jedna grupa będzie miała rację, więc 5 więźniów odpowie poprawnie, a 5 nie.

Zauważ, że więźniowie nie mogą znaleźć strategii gwarantującej uwolnienie więcej niż 5 więźniów. Rzeczywiście, w przypadku jednego więźnia istnieje tyle samo rozkładów kolorów kapeluszy, w których podaje on poprawną odpowiedź, jak w przypadku, gdy tego nie robi. W związku z tym istnieje tyle samo rozkładów kolorów kapeluszy, w których 6 lub więcej więźniów podaje poprawną odpowiedź, niż w przypadku, gdy 4 lub mniej to robi.

Policzalny wariant nieskończonego kapelusza bez słuchu

Opis

W tym wariancie niezliczona liczba więźniów, każdy z nieznanym i losowo przydzielonym czerwonym lub niebieskim kapeluszem, ustawia się w jednej linii. Każdy więzień odwraca się od początku linii, a każdy więzień widzi wszystkie kapelusze przed sobą i żaden z kapeluszy z tyłu. Zaczynając od początku linii, każdy więzień musi poprawnie rozpoznać kolor swojego kapelusza lub zostaje zabity na miejscu. Tak jak wcześniej, więźniowie mają okazję spotkać się wcześniej, ale w przeciwieństwie do poprzednich, w kolejce, żaden więzień nie słyszy, co mówią inni więźniowie. Pytanie brzmi, czy istnieje sposób na zapewnienie, że tylko skończenie wielu więźniów zostanie zabitych?

Rozwiązanie

Jeśli przyjmiemy aksjomat wyboru i założymy, że każdy z więźniów ma (nierealistyczną) zdolność zapamiętywania nieskończonej ilości informacji i wykonywania obliczeń z nieprzeliczalnie nieskończoną złożonością obliczeniową , odpowiedź brzmi: tak. W rzeczywistości, nawet jeśli dopuścimy niezliczoną liczbę różnych kolorów czapek i niezliczoną liczbę więźniów, aksjomat wyboru daje rozwiązanie, które gwarantuje, że tylko skończenie wielu więźniów musi umrzeć, pod warunkiem, że każdy więzień widzi czapki innych więźnia (nie tylko tych, którzy są przed nimi w kolejce), a przynajmniej że każdy więzień widzi prawie wszystkie inne kapelusze. Rozwiązanie dla przypadku dwóch kolorów jest następujące, a rozwiązanie dla przypadku niezliczonej liczby nieskończonych kolorów jest zasadniczo takie samo:

Więźniowie stojący w kolejce tworzą sekwencję zer i jedynek, gdzie 0 oznacza kolor niebieski, a 1 oznacza kolor czerwony. Przed umieszczeniem ich w szeregu więźniowie definiują następującą relację równoważności względem wszystkich możliwych ciągów, w które mogą zostać włączeni: Dwie sekwencje są równoważne, jeśli są identyczne po skończonej liczbie wpisów. Z tej relacji równoważności więźniowie otrzymują zbiór klas równoważności. Zakładając aksjomat wyboru, istnieje zbiór reprezentatywnych sekwencji — po jednej z każdej klasy równoważności. ( Prawie każda konkretna wartość jest niemożliwa do obliczenia, ale aksjomat wyboru implikuje, że istnieje jakiś zestaw wartości, więc zakładamy, że więźniowie mają dostęp do wyroczni .)

Kiedy zostaną umieszczeni w swojej linii, każdy więzień może zobaczyć wszystko oprócz skończonej liczby kapeluszy, a zatem może zobaczyć, do której klasy równoważności należy właściwa sekwencja kapeluszy. (Zakłada się, że każdy więzień może wykonać niezliczoną ilość nieskończonych porównań, aby znaleźć dopasowanie, przy czym każde porównanie klasowe wymaga niezliczonej nieskończonej liczby indywidualnych porównań kapeluszy). Następnie kontynuują odgadywanie koloru kapelusza tak, jakby znajdowali się w reprezentatywnej sekwencji z odpowiedniej klasy równoważności. Ponieważ sekwencja rzeczywista i sekwencja reprezentatywna są w tej samej klasie równoważności, ich wpisy są takie same po pewnej skończonej liczbie N więźniów. Wszyscy więźniowie po tych pierwszych N więźniach są uratowani.

Ponieważ więźniowie nie mają informacji o kolorze własnego kapelusza i odgadują, jaki ma kolor, każdy więzień ma 50% szans na śmierć. Paradoksem może się wydawać, że nieskończona liczba więźniów ma równe szanse na śmierć, a jednak pewne jest, że ginie tylko skończona liczba. Rozwiązanie tego paradoksu polega na tym, że funkcja stosowana do określenia przypuszczenia każdego więźnia nie jest funkcją mierzalną .

Aby to zobaczyć, rozważmy przypadek śmierci zero więźniów. Dzieje się tak wtedy i tylko wtedy, gdy rzeczywista sekwencja jest jedną z wybranych sekwencji reprezentatywnych. Jeśli sekwencje zer i jedynek są postrzegane jako binarne reprezentacje liczby rzeczywistej z zakresu od 0 do 1, reprezentatywne sekwencje tworzą zbiór niemierzalny . (Zbiór ten jest podobny do zbioru Vitali , jedyną różnicą jest to, że klasy równoważności są tworzone w odniesieniu do liczb o skończonej reprezentacji binarnej, a nie wszystkich liczb wymiernych.) Stąd nie można przypisać prawdopodobieństwa zdarzeniu zabicia zero więźniów. Argument jest podobny w przypadku innych skończonych liczb zabijanych więźniów, odpowiadających skończonej liczbie odmian każdego przedstawiciela.

Policzalnie nieskończony problem kapelusza ze słyszeniem

Opis

Ten wariant jest taki sam jak poprzedni, z wyjątkiem tego, że więźniowie słyszą kolory wywoływane przez innych więźniów. Pytanie brzmi, jaka jest optymalna strategia dla więźniów, tak aby jak najmniej z nich umierało w najgorszym przypadku?

Rozwiązanie

Okazuje się, że jeśli pozwoli się więźniom słyszeć kolory wywoływane przez innych więźniów, można zagwarantować życie każdemu więźniowi z wyjątkiem pierwszego, który umrze z prawdopodobieństwem 50%.

Aby to zrobić, definiujemy tę samą relację równoważności jak powyżej i ponownie wybieramy reprezentatywną sekwencję z każdej klasy równoważności. Teraz każdą sekwencję w każdej klasie oznaczamy 0 lub 1. Najpierw oznaczamy sekwencję reprezentatywną 0. Następnie każdą sekwencję, która różni się od sekwencji reprezentatywnej w parzystej liczbie miejsc, oznaczamy 0, i każdy ciąg, który różni się od ciągu reprezentatywnego w nieparzystej liczbie miejsc przez 1. W ten sposób każdy możliwy ciąg nieskończony oznaczyliśmy 0 lub 1 ważną właściwością, że dowolne dwa ciągi różniące się tylko jedną cyfrą mają przeciwne etykiety.

Teraz, kiedy naczelnik prosi pierwszą osobę o podanie koloru, lub w naszej nowej interpretacji, 0 lub 1, po prostu wywołuje etykietę sekwencji, którą widzi. Mając te informacje, każdy po nim może dokładnie określić, jaki jest jego własny kolor kapelusza. Druga osoba widzi wszystko oprócz pierwszej cyfry sekwencji, którą widzi pierwsza osoba. Tak więc, o ile mu wiadomo, istnieją dwie możliwe sekwencje, które pierwsza osoba mogłaby oznaczyć: jedna rozpoczynająca się od 0, a druga rozpoczynająca się od 1. Z powodu naszego schematu etykietowania te dwie sekwencje otrzymałyby przeciwne etykiety, więc w oparciu o na podstawie tego, co mówi pierwsza osoba, druga osoba może określić, który z dwóch możliwych sznurków widziała pierwsza osoba, a tym samym może określić swój własny kolor kapelusza. Podobnie każda kolejna osoba w linii zna każdą cyfrę ciągu oprócz tej odpowiadającej jej własnemu kolorowi kapelusza. On zna tych, którzy byli przed nim, ponieważ zostali wezwani, a tych po nim, ponieważ ich widzi. Mając te informacje, może użyć etykiety wywołanej przez pierwszą osobę, aby określić swój własny kolor kapelusza. W ten sposób wszyscy oprócz pierwszej osoby zawsze odgadują poprawnie.

Wersja Eberta i kody Hamminga

Opis

Wersja problemu Eberta stwierdza, że ​​wszyscy gracze, którzy zgadują, muszą zgadywać w tym samym określonym czasie, ale nie wszyscy gracze muszą zgadywać. Teraz nie wszyscy gracze mogą zgadywać poprawnie, więc gracze wygrywają, jeśli przynajmniej jeden gracz zgadnie, a wszyscy, którzy zgadują, zrobią to poprawnie. Jak gracze mogą zmaksymalizować swoje szanse na wygraną?

Rozwiązanie

Jedna ze strategii rozwiązania tej wersji problemu kapeluszy wykorzystuje kody Hamminga , które są powszechnie używane do wykrywania i korygowania błędów w transmisji danych . Prawdopodobieństwo wygranej będzie znacznie wyższe niż 50%, w zależności od liczby graczy w konfiguracji puzzli: na przykład prawdopodobieństwo wygranej 87,5% dla 7 graczy.

Podobne strategie można zastosować do zespołów o liczebności N = 2 k -1 i osiągnąć współczynnik zwycięstw (2 k -1)/2 k . W ten sposób strategia kodu Hamminga daje większe współczynniki wygranych dla większych wartości N .

W tej wersji problemu każde indywidualne przypuszczenie ma 50% szans na słuszność. Jednak podejście do kodu Hamminga działa poprzez koncentrację błędnych domysłów razem na określonych dystrybucjach kapeluszy. W niektórych przypadkach wszyscy gracze będą zgadywać niepoprawnie; podczas gdy w pozostałych przypadkach tylko jeden gracz odgadnie, ale poprawnie. Chociaż połowa wszystkich domysłów jest nadal błędna, powoduje to, że gracze wygrywają w ponad 50% przypadków.

Pouczający jest prosty przykład tego typu rozwiązania z trzema graczami. Przy trzech graczach istnieje osiem możliwości; w dwóch z nich wszyscy gracze mają ten sam kolor kapelusza, a w pozostałych sześciu dwóch graczy ma jeden kolor, a drugi gracz ma inny kolor.

Gracze mogą zagwarantować, że wygrają w tych ostatnich przypadkach (75% przypadków) za pomocą następującej strategii:

  1. Każdy gracz, który obserwuje dwie czapki w dwóch różnych kolorach, milczy.
  2. Każdy gracz, który obserwuje dwie czapki tego samego koloru, odgaduje kolor przeciwny.

W dwóch przypadkach, w których wszyscy trzej gracze mają ten sam kolor kapeluszy, wszyscy odgadną nieprawidłowo. Ale w pozostałych sześciu przypadkach tylko jeden gracz odgadnie i słusznie, że jego kapelusz jest przeciwieństwem jego kolegów.

Domy Sneetchville

Opis

Sneetches to stworzenia ze słynnej opowieści dr Seussa „The Sneetches”. Istnieją dwa rodzaje Sneetches, gwiaździste i gładkie. Wszyscy Sneetchowie muszą zdać test logiki, aby mieszkać w Sneetchville, które ma ograniczoną liczbę domów i ma surowe prawo mieszkaniowe, zgodnie z którym każdy dom nie może zawierać więcej niż jednego gwiaździstego Sneetcha i jednego gładkiego Sneetcha. Żaden Sneetch nie jest w stanie zobaczyć własnego brzucha, ale nadal widzi brzuchy wszystkich innych Sneetchów. Aby zapobiec dalszemu konfliktowi między Sneetchami, istnieje prawo, które zabrania Sneetchesom dyskutowania o ich brzuchach (zobacz także Nie pytaj, nie mów ). Każdy Sneetch nie może pominąć domu, dopóki nie upewni się, że nie może się do niego wprowadzić. Jeśli Sneetch złamie prawo, zostaje wykonany. Jak Sneetchowie wybierają swoje domy?

Rozwiązanie

Ponieważ wszyscy Sneetches są potencjalnie zagrożeni, jednym z rozwiązań jest spotkanie wszystkich Sneetches na ulicy; model wskazuje domy, a więc drogę, ulicę lub bliskość. Tam zgadzają się przejść w kierunku Sneetches, które wyglądają podobnie i z dala od Sneetches, które wyglądają inaczej; eliminuje to potrzebę konkretnie komunikowania się na temat cech fizycznych, tj. stanu brzucha. Ruch Sneetch zaczyna się od ruchów Browna, ale tak jak w logice problemu zabłoconych dzieci, zamienia się on w zbijanie się, np. jeden Sneetch zmierza w kierunku dwóch podobnych sneetchów, które są przez nie akceptowane lub odrzucane, lub odwrotnie, i ostatecznie jedna przestrzeń stanów dwóch grupuje wyniki, gwiaździsty i gładki. Jeden Sneetch z pierwszej grupy trafia najpierw do każdego domu, potem jeden Sneetch z drugiej grupy trafia do każdego domu.

Zobacz też

Bibliografia