Na pewno wszyscy kojarzą tę starą zagadkę, w której mamy do czynienia z dwoma strażnikami: jeden zawsze kłamie, drugi zawsze mówi prawdę. Nie wiemy, który jest którym i musimy za pomocą jednego pytania ustalić które drzwi prowadzą na wolność, a które na szubienicę.
Dziś czas na zagadkę nieco bardziej skomplikowaną.
Zanim jednak przejdę do sedna, poinformuję moich pleno titulo Czytelników o ważnej zmianie: od tej pory blokuję możliwość komentowania pod zagadkami. Rozwiązania proszę przesyłać za pomocą formularza kontaktowego. Dzięki temu komentujący nie będą sobie nawzajem przeszkadzać (ani pomagać) i każdy będzie mógł sobie sam dotrzeć do rozwiązania.Wróćmy teraz to clue.
Otóż...
Podobnie jak w wyżej wymienionej zagadce, znajdujemy się w zamkniętym pomieszczeniu z dwojgiem drzwi: jedne drzwi prowadzą na wolność, a drugie na szubienicę.
W pomieszczeniu razem z nami znajduje się trzech strażników:
- Jeden zawsze mówi prawdę
- Drugi zawsze kłamie
- Trzeci odpowiada losowo (a więc czasem kłamie, a czasem nie).
Nie wiemy, który jest który.
Naszym zadaniem jest ustalić które drzwi prowadzą na wolność.
Możemy zadać dwa pytania.
Tylko uwaga: nie dwa pytania każdemu ze strażników, tylko dwa pytania łącznie. Można je zadać temu samemu strażnikowi lub dwóm różnym, jednak łączna liczba pytań nie może przekroczyć dwóch.
Czas - start!
Rozwiązanie poprzedniej zagadki
Poprzednia zagadka dotyczyła - nie po raz pierwszy zresztą na tym blogu - więzienia. A konkretnie próbowaliśmy znaleźć metodę na zmaksymalizowanie szans na przeżycie stu więźniów, z których każdy musi odnaleźć swój numer w jednym ze stu pudełek, w nie więcej niż pięćdziesięciu próbach.
Zagadka jest o tyle wredna, że od chwili, kiedy pierwszy z więźniów wejdzie do pomieszczenia z pudełkami, więźniowie nie mogą w żaden sposób komunikować się między sobą.
Sytuacja, zdawałoby się, kompletnie beznadziejna.
A jednak - nie do końca.
Jeżeli każdemu więźniowi przyporządkujemy numer kolejny od jeden do stu, wówczas każdy z więźniów, po wejściu do pokoju z pudełkami, musi:
- Podejść do pudełka, którego numer odpowiada jego własnemu numerowi
- Sprawdzić numer na karteczce w tym pudełku.
- Jeżeli jest to jego własny numer, wiadomo, wychodzi.
- Jeżeli nie, zagląda do pudełka o numerze znalezionym w poprzednim pudełku.
Kroki 2-4 powtarza tak długo, aż znajdzie karteczkę ze swoim numerem, lub (pechowo) odkryje, że w pięćdziesiątym z kolei pudełku nie ma jego numeru.
No i teraz pytanie: w jaki niby sposób tak strategia ma być lepsza od losowej?
Otóż okazuje się, że jest dużo lepsza!
Sprawdźmy teraz, dlaczego.
Zauważmy, że ponieważ każde z pudełek ma w środku dokładnie jedną kartkę, a także, ponieważ zestaw numerów pudełek i numerów na kartkach pokrywają się (jednych i drugich jest dokładnie 100, od jedynki do setki), to numery prędzej czy później się zapętlą, a więc z całą pewnością w końcu dotrzemy do pudełka, w którym będzie liczba oznaczająca pudełko, od którego zaczęliśmy. Skoro zaczęliśmy od pudełka z naszym własnym numerem, oznacza to, że na końcu pętli znajdziemy karteczkę z naszym numerem.
Nie ma innej możliwości.
Proszę to sobie dobrze przetrawić w głowie przed lekturą dalszej części.
Przykład:
Więzień numer 31 zagląda do pudełka numer 31, znajduje tam kartkę z numerem 7. Pudełko nr 7 ma karteczkę z trójką, pudełko #3 - z siedemnastką, pudełko #17 ma w środku 92, wreszcie pudełko numer 92 ma w środku 31. Więzień dotarł do "swojej" karteczki odkrywając zaledwie pięć pudełek.
Jeżeli pętla nie będzie dłuższa niż 50 pudełek, wówczas więzień z całą pewnością dotrze do "swojego" pudełka na czas.
Ile może być pętli dłuższych niż 50 pudełek?
Maksymalnie - jedna! Skoro zużyliśmy już co najmniej 51 pudełek na pętlę, nie da się z pozostałych 49 pudełek skonstruować pętli dłuższej niż 49 pudełek 😉
Innymi słowy jeżeli wśród stu pudełek nie ma pętli dłuższej niż 50, wówczas wszyscy więźniowie odkryją swoje karteczki przy maksymalnie 50 próbach, a co za tym idzie - wszyscy wyjdą na wolność, ku zdumieniu Złego Dyrektora.
Właśnie sprowadziliśmy zagadkę do następującego pytania:
Jakie jest prawdopodobieństwo, że wśród stu pudełek znajdzie się pętla o długości co najmniej 51 elementów?
Wszystkie karteczki mogą być rozłożone na 100! sposobów.
Na ile sposobów możemy uzyskać 51-elementową pętlę?
Pierwszy element pętli możemy wybrać na 100 sposobów. Drugi - na 99. Trzeci na 98. I tak dalej. A więc liczba sposobów na pętlę 51-elementową to 100 x 99 x 98 x ... x 52 x 51 x 50.
Pozostałych 49 elementów może być wylosowane na 49! sposobów.
Mnożąc jedno przez drugie dostajemy 100!. Pamiętajmy jednak, że nasza 51-elementowa pętla może zaczynać się od dowolnego ze swoich 51 elementów, innymi słowy policzyliśmy ją 51 razy. Tak więc faktyczna liczba kombinacji dla pętli 51-elementowej wynosi 100!/51.
Liczba wszystkich kombinacji to 100!
A więc szansa na pętlę dokładnie 51-elementową wynosi 1/51
Rozumując w podobny sposób okaże się, że prawdopodobieństwo uzyskania pętli 52-elementowej wynosi 1/52, 53-elementowej - 1/53 i tak dalej, aż do pętli 100-elementowej, której prawdopodobieństwo uzyskania wynosi 1/100.
Dodajemy te prawdopodobieństwa do siebie:
http://www.wolframalpha.com/input/?i=Sum%5B1%2Fx,+%7Bx,+51,+100%7D%5D
Wynik?
Około 0.688
A więc szanse na to, że więźniowie trafią na cykl dłuższy niż 50 pudełek, to około 68.8%. Reszta, czyli niecałe 31.2% to ich szansa na wydostanie się na wolność.
Odpowiedzieliśmy więc na pytanie główne oraz bonusowe #1.
A co z pytaniem bonusowym #2? Co ma zrobić zaprzyjaźniony strażnik, żeby poprawić sytuację więźniów? Pamiętajmy, że może on zamienić dwie dowolne karteczki miejscami.
Otóż powinien on przejrzeć wszystkie pudełka, sprawdzić, czy najdłuższy łańcuch ma więcej niż 50 elementów i jeżeli tak - przerwać go, czyli na przykład zamienić miejscami karteczki z pudełek leżących "naprzeciwko siebie" w tym łańcuchu. W ten sposób stworzy dwa łańcuchy o długościach równych połowie łańcucha oryginalnego (a więc na pewno nie dłuższe niż 50).
Krótko mówiąc, jeżeli więźniowie przekupią (lub rozkochają w sobie, w ramach walki z korupcją) jednego z klawiszy, mają gwarantowane wyjście na wolność! A jeżeli nie, to mają około 31.2% szans. Nadal dużo więcej, niż początkowe \(8*10^{-31}\)