Vores puslespil opgave sidste måned var at spare en Star Trek overfladeparti på otte ledet af Enterprise Kommunikationschef Løjtnant Uhura (spillet af den sene Nichelle Nichols). Besætningen er fængslet af en fremmed race, Catenati, på en planet i Halskæde Nebula. For at undslippe skal de maksimere deres sandsynlighed for at udføre en opgave, der i første omgang kun ser ud til at give en dyster sandsynlighed for succes.
Besætningen på otte informeres om opgaven, mens de midlertidigt holdes i et fællesrum, hvor de frit kan kommunikere og strategisere. Om et par timer vil de blive ført, en ad gangen, til et rum kaldet roulettekammeret. Dette rum har otte knapper arrangeret i en række, som hver er programmeret til at reagere på et andet besætningsmedlem. For at vildlede besætningen er hver knap tilfældigt forkert mærket med et andet besætningsmedlems navn. Hvert besætningsmedlem må trykke på op til fire af knapperne i vilkårlig rækkefølge. Hver gang de trykker på en knap, vil de se, hvem knappen egentlig tilhører. Inden for deres fire forsøg skal de finde den knap, der er tildelt dem. For at besætningen kan gå fri, skal alle lykkes med denne opgave. Hvis selv en af dem mislykkes, vil alle blive henrettet. Når et besætningsmedlem har fuldført deres forsøg, skal de isoleres uden mulighed for at videregive information til nogen af deres besætningsmedlemmer.
Chancerne for succes synes minimale. Hvis besætningsmedlemmer vælger knapper tilfældigt, vil hver have en chance på 1 til 2 for at finde deres knap. Chancen for at alle otte lykkes er kun 1 ud af 256, eller omkring 0.4 %.
Men de behøver ikke trykke på knapper tilfældigt. En måde at øge sandsynligheden for succes på kunne være at udjævne alle knaptryk på en eller anden måde. Dette bringer os til vores første puslespilsspørgsmål.
Puslespil 1
Hvor meget kan besætningens overlevelsessandsynlighed forbedres, hvis de sørger for, at hver knap trykkes lige ofte (i stedet for at trykke på fire knapper tilfældigt)?
Rob Corlett , JPayette svarede godt på dette, ligesom de gjorde alle de andre spørgsmål. Hvad angår den undvigende centrale idé bag gåderne i denne klumme, Rob Corlett, JPayette og Jouni Seppänen beskrev det smukt, mens Sacha Bugnon bidraget med en computerløsning.
Her er Rob Corletts svar:
En måde at sikre, at hver knap trykkes lige mange gange, er at adskille fangerne i to lige store grupper på 4.
Hver gruppe trykker kun på de knapper, der svarer til medlemmerne af deres gruppe. Så hvis A, B, C og D alle er i samme undergruppe, trykker de kun på knapperne for A, B, C og D.
Dette ændrer problemet til at spørge efter sandsynligheden for, at hver fange tildeles den rigtige gruppe, da de med garanti vil trykke på deres knap med fire eller færre tryk.
Antallet af måder at befolke den første gruppe (og derfor også den anden gruppe) med fire personer er antallet af måder at vælge 4 fra 8 på, hvilket er C(8, 4) = 70. Derfor er det samlede antal måder at at fordele alle i de to grupper er 70.
Der er kun én tildeling, der korrekt allokerer hver fange til den rigtige gruppe, og så sandsynligheden for, at alle er i den rigtige gruppe, og alle fangerne overlever, er 1/70, hvilket er 3.66 gange bedre end 1/256 i den tidligere strategi. [Men det er stadig meget lille: kun en 1.4% chance.]
Puslespil 2
Der er en måde at forbedre de oprindelige dystre odds over 90 gange til omkring 36.5 %, hvilket virker mirakuløst! Denne strategi involverer brugen af sløjfer eller kæder af gæt - deraf referencerne til halskædetågen og Catenati (catena er latin for kæde). I strategiens grundlæggende form starter hvert besætningsmedlem med at trykke på knappen, der bærer deres navn, og fortsætter derefter til knappen, der bærer navnet på det besætningsmedlem, det første knap faktisk tilhørte, og så videre, og opretter en kæde af navne.
Lad os se, hvordan det fungerer i praksis. I diagrammet er knapperne vist med deres etiketter i hvid. De blå bogstaver nedenfor viser de sande ejere af knapperne. Når det første besætningsmedlem, A, kommer ind i roulette-kammeret, trykker hun først på knap A. Dette er C's knap, så hun trykker på knap C næste, så knap E og til sidst knap F, som faktisk er A's egen knap, så hun har med succes fundet den i fire forsøg. Bemærk, at knapperne ACEF danner en lukket sløjfe af fire knapper. Når besætningsmedlemmer C, E og F skiftes til, vil de også gå rundt i det samme lukkede sløjfe, startende fra deres egne respektive steder, og også finde deres egne knapper i fire forsøg.
Dette arrangement har også to mindre løkker med hver to knapper: BD og GH. Disse fire besætningsmedlemmer vil finde deres egne knapper inden for to forsøg. Så med dette arrangement vil alle besætningsmedlemmer få succes, og de vil have fortjent deres frihed. Det er klart, at hvis arrangementet kun indeholder løkker af længde 4 eller mindre, vil alle besætningsmedlemmerne få succes og vil blive befriet. Hvis der derimod er en enkelt løkke på 5 eller mere, vil alle besætningsmedlemmerne på den løkke ikke finde deres knap i fire forsøg, og besætningen vil blive henrettet. For at finde sandsynligheden for succes kan vi finde sandsynligheden for at have en sløjfe på 5, 6, 7 eller 8, lægge dem sammen og trække summen fra 1. Dette er lettere at beregne end den anden vej, fordi for otte knapper, kan der kun være en enkelt sløjfe med 5, 6, 7 eller 8 medlemmer.
Der er 8! forskellige måder at arrangere otte knapper på. Men når vi laver loops, står den samme loop for otte af disse arrangementer (ABCDEFGH danner den samme loop som BCDEFGHA, hvilket er det samme som CDEFGHAB osv.). Så sandsynligheden for at have en løkke med størrelse 8 er (8!/8)/8!, hvilket simpelthen er 1/8. På samme måde er sandsynligheden for at have en løkke i størrelse 7 1/7, af størrelse 6 er 1/6, og størrelse 5 er 1/5. Derfor er sandsynligheden for succes for vores uforfærdede besætning 1 − (1/5 + 1/6 + 1/7 + 1/8), eller 36.5%, som tidligere nævnt.
Ovenstående strategi virker for et hvilket som helst antal fanger, og forbedringen i odds i forhold til den tilfældige tilgang stiger hurtigt, efterhånden som dette antal stiger. Det er omkring syv gange for fire fanger, 24 gange for seks, 93 gange for otte og en forbløffende (3.8 × 10)29)-fold for 100 fanger. Nøglen til at forstå denne enorme stigning er, at metoden binder succes eller fiasko for hvert medlem af gruppen til de andres. I meget høj grad lykkes eller fejler de alle sammen. Gruppens sandsynlighed for succes falder ikke for meget fra en enkelt persons sandsynlighed, idet den kun falder fra 50 % for en enkelt fange til 30.69 %, da antallet af fanger øges uden grænser. På den anden side falder sandsynligheden for, at en tilfældig tilgang eller endda en "lige-knap-tryk"-tilgang lykkes hurtigt til meget tæt på nul for selv et lille antal fanger.
Hvis logikken bag denne strategi stadig virker uklar, er her en analyse af problemet med 100 fanger i dette fremragende video af Veritasium.
Puslespil 3
Dette puslespil handlede om, at løjtnant Uhura huskede et barndomsspil, som i det væsentlige var det samme puslespil, men for seks personer. Som et tip foreslog jeg at løse problemet for fire personer. Nu hvor vi har formlen, kan vi nemt beregne sandsynligheden.
For fire personer er sandsynligheden for, at den længste sløjfe kun er 2 eller 1: 1 − (1/3 + 1/4) eller 41.7 % med en syvfoldig gevinst i forhold til tilfældigt valg.
For seks personer er sandsynligheden for, at den længste sløjfe er 3, 2 eller 1: 1 − (1/4 + 1/5 + 1/6) eller 38.3 % med mere end en 24-fold gevinst i forhold til tilfældigt valg.
Puslespil 4
Som vores historie fortsætter, viser det sig, at en af Catenati har taget en særlig modvilje mod Enterprise besætning og fjernovervåger dem. Han har mistanke om, at de har fundet frem til en effektiv strategi baseret på Uhuras diagram. Han er fast besluttet på at forpurre deres plan ved at glide ind i kammeret og bevidst ændre rækkefølgen af knapetiketterne, før rouletten starter. Kan han med held forpurre planen? Hvad skal den landende part være særlig opmærksom på at skjule?
Meget tidligt i besætningens strategidiskussion kneb Uhuras øjne pludselig sammen. Hun gav et signal til sit mandskab, og hun skiftede til at tale på Nicholese og meddelte: "Alle yderligere diskussioner på Nicholese, tak." Nicholese var et nyt sprog, som Uhura havde opfundet tidligt i sin karriere til netop denne slags situationer, for at omgå brugen af universelle oversættere. "Du må have lagt mærke til den mistænkelige Catenati," fortsatte hun. "Han kunne prøve at sabotere os, så vi er nødt til at ændre vores plan. Her er hvad vi skal gøre…”
Uhura skitserede den nye plan, indtil hun var overbevist om, at hvert medlem af hendes besætning vidste den udmærket. Så tænkte hun, med et fjernt blik i øjnene, "Jeg opkaldte Nicholese efter en ikonisk skuespillerinde fra det 20. århundrede. Jeg er glad for, at jeg insisterede på, at Starfleet gjorde det til standard på alle vores skibe."
Hun vendte sig tilbage til besætningen. "Det er alt, betjente. Du ved hvad du skal gøre!"
Vi ved ikke præcis, hvad Uhura fortalte sit hold. Men JPayette og Rob Corlett havde en ret god idé. Her er Rob Corlett igen:
Hvis den onde Catenati hører, at de bruger denne strategi, kan han skifte navnene vist på displayet for at sikre, at der er en cyklus længere end 4.
For at bryde dette skal fangerne acceptere en hemmelig ordre, som randomiserer sekvensen. Det gør de ved at sige noget som "hvis du ser Uhuras navn, så gå til knappen mærket Chekov. Hvis du ser Chekovs navn vist, skal du gå til knappen mærket Smith osv."
På denne måde betyder omarrangeringen af Catenati ikke noget, da det kun virker, hvis du ved, hvordan besætningen vil reagere på navnene på skærmene. De skal dog holde enhver genbestilling hemmelig, ellers kan den blive brudt igen.
Som vi så, sikrede Uhura, at hemmeligheden ville blive opbevaret sikkert. Hvert medlem af besætningen skulle bare bruge den samme hemmelige ordre og sikre, at den onde Catenati ikke vidste, hvad det var. Faktisk øgede den ændrede rækkefølge af den onde Catenati faktisk besætningens sandsynlighed for at lykkes!
Dette er, hvad der skete. Uhura var den første, der blev taget til roulette-kammeret. Hun trykkede på tre knapper. Ingen var hendes. Skal hun være ked af det eller glad? Hun holdt vejret og trykkede på den fjerde. Hun havde fundet sin rigtige knap!
Hun vidste, at de alle ville blive reddet.
Puslespil 5
Hvilken grænse nærmer den maksimale succesprocent sig, når størrelsen på landingsfesten stiger på ubestemt tid? Kan du forklare, hvorfor denne metode er så meget mere effektiv end tilfældig knaptryk?
JPayette skrev:
Alt ovenstående generaliserer ligefrem til en besætning på 2n medlemmer må højst trykke n knapper. Fra Puslespil 2 udleder vi, at deres chance for succes er
1 - (sum over k mellem n + 1 og 2n af 1/k).
Summen kan sammenlignes med integralet af 1/x over intervallet [n, 2n], hvilket giver os mulighed for at bevise, at som n vokser til det uendelige, falder ovenstående sandsynlighed for at konvergere til forbløffende 1 − ln(2) ≈ 30.6%. [Faktisk 30.69 % til to decimaler.]
Rob Corlett tilføjede:
Kender du ikke integrationen, kan du hurtigt komme frem til et omtrentligt svar ved udregning ved hjælp af et regneark. Jeg nåede 0.307 en gang n nået omkring 750, hvilket er nøjagtigt med 3 decimaler.
Vi har allerede forklaret ovenfor, hvorfor denne metode virker. Alle sløjfer længere end 1 deles af flere besætningsmedlemmer. Så deres succeser og fiaskoer er stærkt korrelerede. Det er en illustration af princippet "Alle for én, og én for alle." Lige ud af Starfleet manualen!
Tak til alle vores bidragydere. JPayette og Rob Corlett indsendte begge prisværdige svar, der fik denne løsningskolonne til at virke næsten overflødig. Ak, jeg må holde mig til vores regel om at vælge en vinder pr. puslespilskolonne. Insights-prisen går til JPayette som en anerkendelse af bidrag her og i det forrige puslespil. Tillykke! Rob Corlett, dine bidrag vil ikke blive glemt.
Vi ses i næste måned for nye indsigter!
