naše ugankarska naloga prejšnji mesec je bilo reševanje a Star Trek površinska zabava osmih pod vodstvom Podjetje Uradnik za komunikacije Poročnik Uhura (igral ga je pokojni Nickelle Nichols). Posadko zapre tuja rasa, Catenati, na planet v Ogrlica Nebula. Da bi pobegnili, morajo čim bolj povečati svojo verjetnost, da bodo opravili nalogo, za katero se sprva zdi, da ponuja le klavrno verjetnost uspeha.
Osemčlanska posadka je obveščena o nalogi, medtem ko je začasno zadržana v skupnem prostoru, kjer lahko prosto komunicirajo in oblikujejo strategije. Čez nekaj ur jih bodo enega za drugim odpeljali v sobo, imenovano komora za ruleto. Ta soba ima osem gumbov, razporejenih v vrsto, od katerih je vsak programiran za odziv na drugega člana posadke. Da bi zavedli posadko, je vsak gumb naključno napačno označen z imenom drugega člana posadke. Vsak član posadke lahko pritisne do štiri gumbe v poljubnem vrstnem redu. Kadar koli pritisnejo gumb, bodo videli, komu gumb v resnici pripada. V svojih štirih poskusih morajo najti gumb, ki jim je dodeljen. Da gre posadka na svobodo, morajo vsi uspeti pri tej nalogi. Če vsaj eden od njih ne uspe, bodo vsi izvedeni. Ko član posadke zaključi svoj poskus, ga je treba izolirati, tako da ne more posredovati informacij nobenemu od svojih članov posadke.
Možnosti za uspeh se zdijo majhne. Če člani posadke naključno izberejo gumbe, bo vsak imel možnost 1 proti 2, da najde svoj gumb. Možnost, da vsem osmim uspe, je le 1 proti 256 ali približno 0.4 %.
Vendar jim ni treba naključno pritiskati gumbov. Eden od načinov za povečanje verjetnosti uspeha bi lahko bil, da na nek način izenačite vse pritiske gumbov. To nas pripelje do našega prvega ugankarskega vprašanja.
Uganka 1
Za koliko se lahko poveča verjetnost preživetja posadke, če zagotovijo, da je vsak gumb pritisnjen enako pogosto (namesto da bi naključno pritisnili katere koli štiri gumbe)?
Rob Corlett in JPayette so na to dobro odgovorili, tako kot na vsa druga vprašanja. Kar zadeva izmuzljivo osrednjo idejo za ugankami v tej kolumni, Rob Corlett, JPayette in Jouni Seppänen lepo opisal, medtem ko Sacha Bugnon prispeval računalniško rešitev.
Tukaj je odgovor Roba Corletta:
Eden od načinov, da zagotovite, da je vsak gumb pritisnjen enako število krat, je, da zapornike razdelite v dve enako veliki skupini po 4.
Vsaka skupina pritisne samo gumbe, ki ustrezajo članom njihove skupine. Torej, če so A, B, C in D vsi v isti podskupini, pritisnejo samo gumbe za A, B, C in D.
To spremeni problem v vprašanje verjetnosti, da je vsak zapornik razporejen v pravo skupino, saj je potem zagotovljeno, da pritisne svoj gumb v štirih ali manj pritiskih.
Število načinov zapolnitve prve skupine (in torej tudi druge skupine) s štirimi osebami je število načinov izbire 4 od 8, kar je C(8, 4) = 70. Zato je skupno število načinov razdelitev vseh v obe skupini je 70.
Obstaja samo ena dodelitev, ki vsakega zapornika pravilno razporedi v pravo skupino, zato je verjetnost, da so vsi v pravi skupini in da vsi zaporniki preživijo, 1/70, kar je 3.66-krat boljše od 1/256 prejšnje strategije. [Vendar je še vedno zelo majhna: le 1.4-odstotna možnost.]
Uganka 2
Obstaja način za izboljšanje prvotnih žalostnih kvot za več kot 90-krat, na približno 36.5%, kar se zdi čudežno! Ta strategija vključuje uporabo zank ali verig ugibanj — od tod tudi sklicevanja na meglico Ogrlica in Catenati (catena je latinsko za verigo). V osnovni obliki strategije vsak član posadke začne s pritiskom na gumb z njegovim imenom, nato nadaljuje z gumbom z imenom člana posadke, ki mu je prvi gumb dejansko pripadal, in tako naprej, tako da se ustvari veriga imen.
Poglejmo, kako to deluje v praksi. Na diagramu so gumbi prikazani z belimi oznakami. Modre črke spodaj prikazujejo prave lastnike gumbov. Ko prvi član posadke, A, vstopi v komoro rulete, najprej pritisne gumb A. To je gumb C, zato pritisne gumb C, nato gumb E in nazadnje gumb F, ki je pravzaprav lasten gumb A, tako da ga je uspešno našla v štirih poskusih. Upoštevajte, da gumbi ACEF tvorijo zaprto zanko štirih gumbov. Ko se člani posadke C, E in F izmenjujejo, bodo prav tako šli okoli iste zaprte zanke, začenši s svojih mest, in v štirih poskusih prav tako našli svoje gumbe.
Ta ureditev ima tudi dve manjši zanki s po dvema gumboma: BD in GH. Ti štirje člani posadke bodo našli svoje gumbe v dveh poskusih. Torej bodo s to ureditvijo vsi člani posadke uspešni in si bodo prislužili svobodo. Jasno je, da če aranžma vsebuje samo zanke dolžine 4 ali manj, bodo vsi člani posadke uspešni in bodo osvobojeni. Če pa obstaja ena sama zanka s 5 ali več, potem vsi člani posadke v tej zanki ne bodo našli svojega gumba v štirih poskusih in posadka bo usmrčena. Da bi našli verjetnost uspeha, lahko poiščemo verjetnost, da imamo zanko 5, 6, 7 ali 8, jih seštejemo in to vsoto odštejemo od 1. To je lažje izračunati kot drugače, ker za osem gumbov, je lahko samo ena zanka s 5, 6, 7 ali 8 členi.
8 jih je! različne načine za razporeditev osmih gumbov. Toda ko naredimo zanke, ista zanka predstavlja osem teh ureditev (ABCDEFGH tvori isto zanko kot BCDEFGHA, kar je enako kot CDEFGHAB itd.). Torej je verjetnost, da imamo zanko velikosti 8 (8!/8)/8!, kar je preprosto 1/8. Podobno je verjetnost, da imamo zanko velikosti 7, 1/7, velikosti 6 1/6 in velikosti 5 1/5. Zato je verjetnost uspeha naše neustrašne posadke 1 − (1/5 + 1/6 + 1/7 + 1/8) ali 36.5 %, kot smo že omenili.
Zgornja strategija deluje za poljubno število zapornikov in izboljšanje verjetnosti v primerjavi z naključnim pristopom hitro narašča, ko to število narašča. To je približno sedemkratno za štiri zapornike, 24-kratno za šest, 93-kratno za osem in osupljivo (3.8 × 1029)-krat za 100 jetnikov. Ključ do razumevanja tega ogromnega povečanja je, da metoda povezuje uspeh ali neuspeh vsakega člana skupine z uspehom ali neuspehom drugih. V zelo veliki meri vsi skupaj uspejo ali propadejo. Verjetnost uspeha skupine ne pade preveč v primerjavi z možnostjo ene osebe, saj pade le s 50 % za enega zapornika na 30.69 %, ko se število zapornikov neomejeno povečuje. Po drugi strani pa verjetnost uspešnega naključnega pristopa ali celo pristopa »enakomernih pritiskov gumbov« hitro upade zelo blizu ničle za celo majhno število zapornikov.
Če se logika v ozadju te strategije še vedno zdi nejasna, je tukaj analiza problema 100 zapornikov v tem odličen video Veritasium.
Uganka 3
Ta uganka je govorila o tem, da se je poročnik Uhura spominjal igre iz otroštva, ki je bila v bistvu enaka uganka, vendar za šest ljudi. Kot namig sem predlagal reševanje problema za štiri osebe. Zdaj, ko imamo formulo, lahko enostavno izračunamo verjetnosti.
Za štiri osebe je verjetnost, da je najdaljša zanka samo 2 ali 1: 1 − (1/3 + 1/4) ali 41.7 % s sedemkratnim dobitkom v primerjavi z naključno izbiro.
Za šest ljudi je verjetnost, da je najdaljša zanka 3, 2 ali 1: 1 − (1/4 + 1/5 + 1/6) ali 38.3 % z več kot 24-kratnim dobitkom v primerjavi z naključno izbiro.
Uganka 4
Ko se naša zgodba nadaljuje, se izkaže, da je eden od Catenatov še posebej ne maral Podjetje posadke in jih daljinsko spremlja. Sumi, da so na podlagi Uhurinega diagrama iznašli neko učinkovito strategijo. Odločen je prekrižati njihov načrt tako, da zdrsne v dvorano in namerno spremeni vrstni red nalepk na gumbih, preden se ruleta začne. Ali lahko uspešno prekriža načrt? Kaj mora biti desant še posebej pozoren, da prikrije?
Zelo zgodaj med razpravo o strategiji posadke so se Uhurine oči nenadoma zožile. Dala je znak svoji posadki in prešla na govorjenje v nicholeseju ter sporočila: "Vse nadaljnje razprave v nicholeseju, prosim." Nicholese je bil nov jezik, ki ga je Uhura izumila na začetku svoje kariere prav za tovrstne situacije, da bi se izognila uporabi univerzalnih prevajalnikov. »Gotovo ste opazili tistega sumljivega Catenatija,« je nadaljevala. »Lahko bi nas poskusil sabotirati, zato moramo spremeniti naš načrt. Tukaj je tisto, kar moramo storiti …”
Uhura je orisala nov načrt, dokler se ni prepričala, da ga vsi člani njene posadke dobro poznajo. Potem je z odmaknjenim pogledom v očeh razmišljala: »Nicholese sem poimenovala po ikonični igralki 20. stoletja. Vesel sem, da sem vztrajal, da je Zvezdna flota standard na vseh naših ladjah.”
Obrnila se je nazaj k posadki. »To je vse, policisti. Veš kaj storiti!"
Ne vemo natančno, kaj je Uhura povedala svoji ekipi. Toda JPayette in Rob Corlett sta imela zelo dobro idejo. Tukaj je spet Rob Corlett:
Če zlobni Catenati sliši, da uporabljajo to strategijo, lahko zamenja imena, prikazana na zaslonu, da zagotovi, da je cikel daljši od 4.
Da bi to prekinili, se morajo zaporniki strinjati s skrivnim ukazom, ki naključno določa zaporedje. To naredijo tako, da rečejo nekaj takega: »če vidite Uhurino ime, pojdite na gumb z oznako Chekov. Če vidite prikazano Chekovljevo ime, pojdite na gumb z oznako Smith itd.«
Na ta način prerazporeditev s strani Catenati ni pomembna, saj deluje le, če poznate način, na katerega se bo posadka odzvala na imena na zaslonih. Morebitno prerazporeditev pa morajo ohraniti v skrivnosti, sicer se lahko spet pokvari.
Kot smo videli, je Uhura zagotovil, da bo skrivnost varovana. Vsak član posadke je moral samo uporabiti isti tajni ukaz in zagotoviti, da zlobni Catenati ne ve, kaj je to. Pravzaprav je spremenjeni vrstni red zlobnega Catenatija dejansko povečal verjetnost uspeha posadke!
To se je zgodilo. Uhura je bil prvi, ki so ga odpeljali v komoro za ruleto. Pritisnila je tri gumbe. Nobena ni bila njena. Naj bo žalostna ali vesela? Zadržala je dih in pritisnila na četrto. Našla je svoj pravi gumb!
Vedela je, da bodo vsi rešeni.
Uganka 5
Kateri meji se približuje najvišji odstotek uspeha, ko se velikost pristajalne skupine povečuje za nedoločen čas? Ali lahko pojasnite, zakaj je ta metoda toliko učinkovitejša od naključnega pritiskanja gumbov?
JPayette je napisal/a:
Vse zgoraj navedeno se neposredno posploši na 2-člansko posadkon vsak član lahko pritisne največ n gumbi. Iz Puzzle 2 sklepamo, da je njihova možnost za uspeh
1 − (vsota čez k med n + 1 in 2n od 1/k).
Vsoto lahko primerjamo z integralom 1/x čez interval [n, 2n], kar nam omogoča, da dokažemo, da kot n raste do neskončnosti, se zgornja verjetnost zmanjša in konvergira na osupljivo 1 − ln(2) ≈ 30.6 %. [Pravzaprav 30.69 % na dve decimalni mesti natančno.]
Rob Corlett je dodal:
Če integracije ne poznate, lahko hitro pridete do približnega odgovora z izračunom s pomočjo preglednice. Enkrat sem prišel do 0.307 n dosegel približno 750, kar je natančno 3 decimalna mesta.
Zgoraj smo že pojasnili, zakaj ta metoda deluje. Vse zanke, daljše od 1, si deli več članov posadke. Torej so njihovi uspehi in neuspehi močno povezani. To je ilustracija načela "Vsi za enega in eden za vse." Naravnost iz priročnika Zvezdne flote!
Hvala vsem našim sodelavcem. JPayette in Rob Corlett sta predložila nagrajena odgovora, zaradi katerih se je ta stolpec z rešitvami zdel skoraj odveč. Žal se moram držati našega pravila, da izberemo enega zmagovalca na stolpec uganke. Nagrado Insights prejme JPayette kot priznanje za prispevke tukaj in v prejšnji uganki. čestitke! Rob Corlett, vaši prispevki ne bodo pozabljeni.
Se vidimo naslednji mesec za nove vpoglede!
