Autonomiczne zadanie logiczne w zeszłym miesiącu było zaoszczędzenie Star Trek partia powierzchniowa ośmiu prowadzona przez Enterprise Komunikacja Officer Porucznik Uhura (grany przez późnego) Nicole Nichols). Załoga zostaje uwięziona przez obcą rasę, Catenati, na planecie w Naszyjnik Mgławica. Aby uciec, muszą zmaksymalizować prawdopodobieństwo wykonania zadania, które na pierwszy rzut oka wydaje się oferować jedynie marne prawdopodobieństwo sukcesu.
Ośmioosobowa załoga jest informowana o zadaniu, gdy jest tymczasowo przetrzymywana we wspólnym pokoju, gdzie może swobodnie komunikować się i opracowywać strategie. Za kilka godzin zostaną zaprowadzeni, pojedynczo, do pomieszczenia zwanego komorą ruletki. Ten pokój ma osiem przycisków ułożonych w rzędzie, z których każdy jest zaprogramowany tak, aby odpowiadał innemu członkowi załogi. Aby wprowadzić w błąd załogę, każdy przycisk jest losowo błędnie oznaczony imieniem innego członka załogi. Każdy członek załogi może nacisnąć maksymalnie cztery przyciski w dowolnej kolejności. Za każdym razem, gdy nacisną przycisk, zobaczą, do kogo tak naprawdę należy. W ciągu czterech prób muszą znaleźć przypisany im przycisk. Aby załoga wyszła na wolność, wszyscy muszą odnieść sukces w tym zadaniu. Jeśli choć jeden z nich zawiedzie, wszystkie zostaną wykonane. Po tym, jak członek załogi zakończy próbę, należy go odizolować bez możliwości przekazania informacji żadnemu z członków załogi.
Szanse na sukces wydają się znikome. Jeśli członkowie załogi wybierają przyciski losowo, każdy z nich będzie miał szansę 1 na 2 na znalezienie swojego przycisku. Szansa na sukces wszystkich ośmiu wynosi tylko 1 na 256, czyli około 0.4%.
Ale nie muszą losowo naciskać przycisków. Jednym ze sposobów na zwiększenie prawdopodobieństwa sukcesu może być w jakiś sposób wyrównanie wszystkich naciśnięć przycisków. To prowadzi nas do naszego pierwszego zagadkowego pytania.
Łamigłówka 1
O ile można zwiększyć prawdopodobieństwo przetrwania załogi, jeśli upewni się, że każdy przycisk jest wciskany tak samo często (zamiast wciskania dowolnych czterech przycisków losowo)?
Roba Corletta i JPayette odpowiedzieli na to dobrze, podobnie jak na wszystkie inne pytania. Jeśli chodzi o nieuchwytną główną ideę zagadek w tej kolumnie, Rob Corlett, JPayette i Jouni Seppänen opisał to pięknie, podczas gdy Sacha Bugnon wniósł rozwiązanie komputerowe.
Oto odpowiedź Roba Corletta:
Jednym ze sposobów zapewnienia, że każdy przycisk zostanie naciśnięty tyle samo razy, jest podzielenie więźniów na dwie równej wielkości grupy po 4.
Każda grupa naciska tylko przyciski odpowiadające członkom jej grupy. Tak więc, jeśli A, B, C i D są w tej samej podgrupie, naciskają tylko przyciski dla A, B, C i D.
To zmienia problem w pytanie o prawdopodobieństwo, że każdy więzień zostanie przydzielony do właściwej grupy, ponieważ wtedy ma gwarancję, że naciśnie swój przycisk w czterech lub mniej naciśnięciach.
Liczba sposobów zapełnienia pierwszej grupy (a więc i drugiej grupy) czterema osobami to liczba sposobów wyboru 4 z 8, czyli C(8, 4) = 70. Zatem łączna liczba sposobów przydzielenie wszystkich do dwóch grup wynosi 70.
Jest tylko jeden przydział, który prawidłowo przypisuje każdego więźnia do właściwej grupy, a więc prawdopodobieństwo, że wszyscy znajdą się we właściwej grupie i wszyscy więźniowie przeżyją, wynosi 1/70, co jest 3.66 razy lepsze niż 1/256 w poprzedniej strategii. [Ale nadal jest bardzo mały: tylko 1.4% szansy.]
Łamigłówka 2
Istnieje sposób na zwiększenie pierwotnych ponurych szans ponad 90-krotnie, do około 36.5%, co wydaje się cudem! Ta strategia polega na wykorzystaniu pętli lub łańcuchów domysłów — stąd odniesienia do Mgławicy Naszyjnik i Catenati (łańcuch to po łacinie łańcuch). W podstawowej formie strategii każdy członek załogi zaczyna od wciśnięcia przycisku z jego nazwiskiem, następnie przechodzi do przycisku z nazwiskiem członka załogi, do którego faktycznie należał pierwszy przycisk, i tak dalej, tworząc łańcuch imion.
Zobaczmy, jak to działa w praktyce. Na schemacie przyciski są pokazane z ich etykietami w kolorze białym. Niebieskie litery poniżej pokazują prawdziwych właścicieli przycisków. Kiedy pierwszy członek załogi, A, wchodzi do komory ruletki, najpierw naciska przycisk A. To jest przycisk C, więc wciska przycisk C, potem przycisk E, a na końcu przycisk F, który w rzeczywistości jest własnym przyciskiem A, więc udało jej się go znaleźć w czterech próbach. Zauważ, że przyciski ACEF tworzą zamkniętą pętlę czterech przycisków. Kiedy członkowie załogi C, E i F wykonują swoje tury, będą również poruszać się po tej samej zamkniętej pętli, zaczynając od swoich odpowiednich miejsc, a także znaleźć własne przyciski w czterech próbach.
Ten układ ma również dwie mniejsze pętle po dwa przyciski: BD i GH. Tych czterech członków załogi znajdzie własne przyciski w ciągu dwóch prób. Tak więc dzięki temu rozwiązaniu wszyscy członkowie załogi odniosą sukces i zasłużą na wolność. Oczywiste jest, że jeśli układ zawiera tylko pętle o długości 4 lub mniejszej, wszyscy członkowie załogi odniosą sukces i zostaną uwolnieni. Jeśli, z drugiej strony, jest jedna pętla z 5 lub więcej, wtedy wszyscy członkowie załogi w tej pętli nie zdołają znaleźć swojego przycisku w czterech próbach, a załoga zostanie wykonana. Aby znaleźć prawdopodobieństwo sukcesu, możemy znaleźć prawdopodobieństwo wystąpienia pętli 5, 6, 7 lub 8, dodać je i odjąć tę sumę od 1. Jest to łatwiejsze do obliczenia niż w inny sposób, ponieważ dla ośmiu przycisków, może istnieć tylko jedna pętla mająca 5, 6, 7 lub 8 członków.
Jest 8! różne sposoby rozmieszczenia ośmiu przycisków. Ale kiedy tworzymy pętle, ta sama pętla odpowiada za osiem z tych układów (ABCDEFGH tworzy tę samą pętlę co BCDEFGHA, która jest taka sama jak CDEFGHAB itp.). Zatem prawdopodobieństwo posiadania pętli o rozmiarze 8 wynosi (8!/8)/8!, czyli po prostu 1/8. Podobnie prawdopodobieństwo posiadania pętli o rozmiarze 7 wynosi 1/7, rozmiaru 6 to 1/6, a rozmiaru 5 to 1/5. Dlatego prawdopodobieństwo sukcesu naszej nieustraszonej załogi wynosi 1 − (1/5 + 1/6 + 1/7 + 1/8), czyli 36.5%, jak wspomniano wcześniej.
Powyższa strategia działa dla dowolnej liczby więźniów, a poprawa szans w porównaniu z podejściem losowym gwałtownie wzrasta wraz ze wzrostem tej liczby. To około siedmiokrotny dla czterech więźniów, 24-krotny dla sześciu, 93-krotny dla ośmiu i zadziwiający (3.8 × 10).29)-krotnie za 100 więźniów. Kluczem do zrozumienia tego ogromnego wzrostu jest to, że metoda wiąże sukces lub porażkę każdego członka grupy z sukcesami pozostałych. W bardzo dużym stopniu wszyscy razem odnoszą sukces lub porażkę. Prawdopodobieństwo sukcesu grupy nie spada zbytnio w porównaniu z pojedynczą osobą, spadając tylko z 50% dla jednego więźnia do 30.69%, ponieważ liczba osadzonych wzrasta bez ograniczeń. Z drugiej strony, prawdopodobieństwo przypadkowego podejścia, a nawet „naciśnięcia parzystego przycisku” szybko spada do bardzo bliskiego zeru nawet dla niewielkiej liczby więźniów.
Jeśli logika stojąca za tą strategią nadal wydaje się niejasna, oto analiza problemu 100 więźniów w tym przypadku doskonały film Veritasium.
Łamigłówka 3
Ta łamigłówka dotyczyła wspomnienia porucznika Uhury z dziecięcej gry, która była zasadniczo tą samą łamigłówką, ale dla sześciu osób. Jako podpowiedź zasugerowałem rozwiązanie problemu dla czterech osób. Teraz, gdy mamy formułę, możemy łatwo obliczyć prawdopodobieństwa.
Dla czterech osób prawdopodobieństwo, że najdłuższa pętla to tylko 2 lub 1, wynosi: 1 − (1/3 + 1/4) lub 41.7% z siedmiokrotnym wzrostem w porównaniu z wyborem losowym.
Dla sześciu osób prawdopodobieństwo, że najdłuższa pętla to 3, 2 lub 1 wynosi: 1 − (1/4 + 1/5 + 1/6) lub 38.3% z ponad 24-krotnym wzrostem w stosunku do losowego wyboru.
Łamigłówka 4
Gdy nasza historia toczy się dalej, okazuje się, że jeden z Catenati miał szczególną niechęć do Enterprise załogi i zdalnie je monitoruje. Podejrzewa, że wymyślili jakąś skuteczną strategię opartą na diagramie Uhury. Jest zdeterminowany, aby udaremnić ich plan, wślizgując się do komory i celowo zmieniając kolejność etykiet przycisków przed rozpoczęciem ruletki. Czy uda mu się pokrzyżować plan? Co zwiad musi szczególnie starannie ukryć?
Na samym początku dyskusji nad strategią załogi oczy Uhury nagle się zwęziły. Dała sygnał swojej załodze i przeszła na mówienie po nicholese, ogłaszając: „Cała dalsza dyskusja po nicholese, proszę”. Nicholese był nowym językiem, który Uhura wymyśliła na początku swojej kariery dla tego rodzaju sytuacji, aby obejść użycie uniwersalnych tłumaczy. — Musiałeś zauważyć tego podejrzanego Catenati — ciągnęła. „Mógł spróbować nas sabotować, więc musimy zmodyfikować nasz plan. Oto, co musimy zrobić… ”
Uhura przedstawiła nowy plan, dopóki nie upewniła się, że wszyscy członkowie jej załogi znają go doskonale. Potem zadumała się z odległym spojrzeniem: „Nicholese nazwałam po kultowej dwudziestowiecznej aktorce. Cieszę się, że nalegałem, aby Gwiezdna Flota uczyniła to standardem na wszystkich naszych statkach.
Odwróciła się do załogi. — To wszystko, oficerowie. Wiesz co robić!"
Nie wiemy dokładnie, co Uhura powiedziała swojemu zespołowi. Ale JPayette i Rob Corlett mieli całkiem niezły pomysł. Oto znowu Rob Corlett:
Jeśli zły Catenati usłyszy, że stosuje tę strategię, może zamienić nazwy wyświetlane na wyświetlaczu, aby upewnić się, że cykl jest dłuższy niż 4.
Aby to przerwać, więźniowie muszą zgodzić się na tajny rozkaz, który losuje sekwencję. Robią to, mówiąc coś w stylu „jeśli zobaczysz imię Uhury, idź do przycisku oznaczonego jako Chekov. Jeśli zobaczysz wyświetlone imię Czechowa, przejdź do przycisku oznaczonego Kowalski itp.”
W ten sposób zmiana kolejności przez Catenati nie ma znaczenia, ponieważ działa tylko wtedy, gdy znasz sposób, w jaki załoga zareaguje na nazwiska na wyświetlaczach. Muszą jednak zachować w tajemnicy wszelkie zmiany kolejności, w przeciwnym razie mogą zostać ponownie złamane.
Jak widzieliśmy, Uhura zapewniła, że sekret będzie bezpieczny. Każdy członek załogi musiał tylko użyć tego samego tajnego rozkazu i upewnić się, że zła Catenati nie wie, co to jest. W rzeczywistości zmieniony rozkaz przez złego Catenati zwiększył prawdopodobieństwo sukcesu załogi!
To jest to, co się stało. Uhura była pierwszą zabraną do komory ruletki. Nacisnęła trzy guziki. Żaden nie był jej. Czy powinna być smutna czy zadowolona? Wstrzymała oddech i nacisnęła czwarty. Znalazła swój prawdziwy guzik!
Wiedziała, że wszyscy zostaną uratowani.
Łamigłówka 5
Do jakiej granicy zbliża się maksymalny procent sukcesu, gdy wielkość zwiadu rośnie w nieskończoność? Czy możesz wyjaśnić, dlaczego ta metoda jest o wiele bardziej wydajna niż losowe wciskanie przycisków?
JPayette napisał:
Wszystkie powyższe uogólniają się wprost na załogę 2n każdy z członków mógł naciskać najwyżej n guziki. Z Puzzle 2 wnioskujemy, że ich szansa na sukces wynosi
1 − (suma nad k pomiędzy n + 1 i 2n 1 /k).
Sumę można porównać z całką 1/x w przedziale [n, 2n], co pozwala nam wykazać, że jako n rośnie do nieskończoności, powyższe prawdopodobieństwo maleje do zadziwiającego 1 − ln(2) ≈ 30.6%. [Właściwie 30.69% do dwóch miejsc po przecinku.]
Rob Corlett dodał:
Jeśli nie znasz integracji, możesz szybko uzyskać przybliżoną odpowiedź, obliczając ją za pomocą arkusza kalkulacyjnego. Raz dostałem 0.307 n osiągnął około 750, co jest z dokładnością do 3 miejsc po przecinku.
Wyjaśniliśmy już powyżej, dlaczego ta metoda działa. Wszystkie pętle dłuższe niż 1 są współdzielone przez wielu członków załogi. Ich sukcesy i porażki są więc silnie skorelowane. Jest to ilustracja zasady „Wszyscy za jednego, jeden za wszystkich”. Prosto z podręcznika Gwiezdnej Floty!
Dziękuję wszystkim naszym współpracownikom. JPayette i Rob Corlett przesłali godne nagrody odpowiedzi, które sprawiły, że ta kolumna z rozwiązaniami wydawała się prawie zbędna. Niestety, muszę trzymać się naszej zasady wyboru jednego zwycięzcy na kolumnę łamigłówki. Nagroda Insights trafia do JPayette w uznaniu wkładu tutaj i poprzedniej układanki. Gratulacje! Rob Corlett, twój wkład nie zostanie zapomniany.
Do zobaczenia w przyszłym miesiącu, aby poznać nowe statystyki!
