Vår puslespill oppgave forrige måned var å spare en Star Trek overflateparti på åtte ledet av Enterprise Kommunikasjonssjef Løytnant Uhura (spilt av sent Nicole Nichols). Mannskapet er fengslet av en fremmed rase, Catenati, på en planet i Halskjede Nebula. For å unnslippe, må de maksimere sannsynligheten for å utføre en oppgave som til å begynne med bare ser ut til å gi en dyster sannsynlighet for å lykkes.
Mannskapet på åtte blir informert om oppgaven mens de midlertidig holdes i et fellesrom hvor de står fritt til å kommunisere og legge strategier. Om noen timer vil de bli ført, en om gangen, til et rom som kalles rulettkammeret. Dette rommet har åtte knapper arrangert på rad, som hver er programmert til å svare på et annet besetningsmedlem. For å villede mannskapet er hver knapp tilfeldig feilmerket med et annet mannskapsmedlems navn. Hvert besetningsmedlem har lov til å trykke på opptil fire av knappene, i hvilken som helst rekkefølge. Hver gang de trykker på en knapp, vil de se hvem knappen egentlig tilhører. I løpet av de fire forsøkene deres må de finne knappen som er tildelt dem. For at mannskapet skal gå fri, må alle lykkes med denne oppgaven. Hvis til og med en av dem mislykkes, vil alle bli henrettet. Etter at et besetningsmedlem har fullført forsøket sitt, skal de isoleres uten noen måte å gi informasjon til noen av besetningskameratene.
Sjansene for suksess virker små. Hvis besetningsmedlemmer velger knapper tilfeldig, vil hver av dem ha 1 av 2 sjanse til å finne knappen sin. Sjansen for at alle åtte lykkes er bare 1 av 256, eller omtrent 0.4 %.
Men de trenger ikke å trykke på knappene tilfeldig. En måte å øke sannsynligheten for suksess på kan være å jevne ut alle knappetrykkene på en eller annen måte. Dette bringer oss til vårt første gåtespørsmål.
Puslespill 1
Hvor mye kan mannskapets overlevelsessannsynlighet forbedres hvis de sørger for at hver knapp trykkes like ofte (i stedet for å trykke tilfeldig på fire knapper)?
Rob Corlett og JPayette svarte godt på dette, som de gjorde alle de andre spørsmålene. Når det gjelder den unnvikende sentrale ideen bak gåtene i denne spalten, Rob Corlett, JPayette og Jouni Seppänen beskrev det vakkert, mens Sacha Bugnon bidratt med en dataløsning.
Her er Rob Corletts svar:
En måte å sikre at hver knapp trykkes like mange ganger er å dele fangene i to like store grupper på 4.
Hver gruppe trykker kun på knappene som tilsvarer medlemmene i gruppen deres. Derfor, hvis A, B, C og D alle er i samme undergruppe, trykker de bare på knappene for A, B, C og D.
Dette endrer problemet til å spørre etter sannsynligheten for at hver fange blir tildelt den riktige gruppen, da de garantert vil trykke på knappen sin med fire eller færre trykk.
Antall måter å befolke den første gruppen (og derfor også den andre gruppen) med fire personer er antall måter å velge 4 fra 8 som er C(8, 4) = 70. Derfor er det totale antallet måter å velge mellom. å fordele alle i de to gruppene er 70.
Det er bare én allokering som korrekt allokerer hver fange til riktig gruppe, og derfor er sannsynligheten for at alle er i riktig gruppe og alle fangene overlever 1/70, som er 3.66 ganger bedre enn 1/256 i forrige strategi. [Men den er fortsatt veldig liten: bare en sjanse på 1.4 %.]
Puslespill 2
Det er en måte å forbedre den opprinnelige dystre oddsen over 90 ganger, til omtrent 36.5 %, noe som virker mirakuløst! Denne strategien innebærer bruk av løkker eller kjeder av gjetninger - derav referansene til halskjedetåken og Catenati (Catena er latin for kjede). I den grunnleggende formen for strategien starter hvert besetningsmedlem med å trykke på knappen som bærer navnet deres, og går deretter videre til knappen som bærer navnet på besetningsmedlemmet den første knappen faktisk tilhørte, og så videre, og oppretter en kjede med navn.
La oss se hvordan dette fungerer i praksis. I diagrammet er knappene vist med etikettene i hvitt. De blå bokstavene nedenfor viser de sanne eierne av knappene. Når det første besetningsmedlemmet, A, kommer inn i rulettkammeret, trykker hun først på knappen A. Dette er Cs knapp, så hun trykker på knappen C neste, deretter knappen E og til slutt knappen F, som faktisk er As egen knapp, så hun har funnet den på fire forsøk. Merk at knappene A-C-E-F danner en lukket sløyfe med fire knapper. Når besetningsmedlemmene C, E og F går på tur, vil de også gå rundt den samme lukkede sløyfen, med start fra sine egne respektive steder, og også finne sine egne knapper i fire forsøk.
Dette arrangementet har også to mindre løkker med to knapper hver: B-D og G-H. Disse fire besetningsmedlemmene vil finne sine egne knapper innen to forsøk. Så med denne ordningen vil alle besetningsmedlemmene lykkes, og de vil ha fortjent sin frihet. Det er klart at hvis arrangementet bare inneholder løkker med lengde 4 eller mindre, vil alle besetningsmedlemmene lykkes og vil bli frigjort. Hvis det derimot er en enkelt sløyfe på 5 eller mer, vil ikke alle besetningsmedlemmene på den løkken finne knappen sin på fire forsøk, og besetningen vil bli henrettet. For å finne sannsynligheten for suksess, kan vi finne sannsynligheten for å ha en sløyfe på 5, 6, 7 eller 8, legge dem sammen og trekke den summen fra 1. Dette er lettere å beregne enn den andre veien fordi for åtte knapper, kan det bare være en enkelt løkke med 5, 6, 7 eller 8 medlemmer.
Det er 8! forskjellige måter å ordne åtte knapper på. Men når vi lager looper, står den samme loopen for åtte av disse arrangementene (ABCDEFGH danner samme loop som BCDEFGHA, som er det samme som CDEFGHAB osv.). Så sannsynligheten for å ha en løkke med størrelse 8 er (8!/8)/8!, som rett og slett er 1/8. På samme måte er sannsynligheten for å ha en løkke med størrelse 7 1/7, størrelse 6 er 1/6 og størrelse 5 er 1/5. Derfor er sannsynligheten for suksess for vårt uforferdede mannskap 1 − (1/5 + 1/6 + 1/7 + 1/8), eller 36.5 %, som nevnt tidligere.
Strategien ovenfor fungerer for et hvilket som helst antall fanger, og forbedringen i oddsen i forhold til den tilfeldige tilnærmingen øker raskt etter hvert som antallet øker. Det er omtrent syv ganger for fire fanger, 24 ganger for seks, 93 ganger for åtte og en forbløffende (3.8 × 10)29)-fold for 100 fanger. Nøkkelen til å forstå denne enorme økningen er at metoden binder suksessen eller fiaskoen til hvert medlem av gruppen til de andres. I svært stor grad lykkes eller mislykkes de alle sammen. Gruppens sannsynlighet for suksess faller ikke for mye fra en enkelt person, og faller bare fra 50 % for en enkelt fange til 30.69 % ettersom antall fanger økes uten grenser. På den annen side avtar sannsynligheten for at en tilfeldig tilnærming eller til og med en "like-knapp-trykk"-tilnærming lykkes raskt til svært nær null for selv et lite antall fanger.
Hvis logikken bak denne strategien fortsatt virker uklar, her er en analyse av 100-fangeproblemet i dette utmerket video av Veritasium.
Puslespill 3
Dette puslespillet handlet om at løytnant Uhura husket et barndomsspill, som egentlig var det samme puslespillet, men for seks personer. Som et hint foreslo jeg å løse problemet for fire personer. Nå som vi har formelen, kan vi enkelt beregne sannsynlighetene.
For fire personer er sannsynligheten for at den lengste sløyfen bare er 2 eller 1: 1 − (1/3 + 1/4) eller 41.7 % med en syvdobling i forhold til tilfeldig valg.
For seks personer er sannsynligheten for at den lengste sløyfen er 3, 2 eller 1: 1 − (1/4 + 1/5 + 1/6) eller 38.3 % med mer enn en 24 gangers gevinst i forhold til tilfeldig valg.
Puslespill 4
Ettersom historien vår fortsetter, viser det seg at en av Catenati har mislikt dem spesielt Enterprise mannskap og fjernovervåker dem. Han mistenker at de har kommet opp med en effektiv strategi basert på Uhuras diagram. Han er fast bestemt på å stoppe planen deres ved å skli inn i kammeret og bevisst endre rekkefølgen på knappeetikettene før ruletten starter. Kan han forpurre planen? Hva må landingsparten være spesielt nøye med å skjule?
Veldig tidlig i mannskapets strategidiskusjon smalt øynene til Uhura plutselig. Hun ga et signal til mannskapet sitt, og hun gikk over til å snakke i Nicholese, og kunngjorde: "All videre diskusjon i Nicholese, vær så snill." Nicholese var et nytt språk Uhura hadde funnet opp tidlig i karrieren for akkurat denne typen situasjoner, for å omgå bruken av universelle oversettere. "Du må ha lagt merke til den mistenkelige Catenati," fortsatte hun. «Han kunne prøve å sabotere oss, så vi må endre planen vår. Her er hva vi må gjøre..."
Uhura skisserte den nye planen til hun var fornøyd med at hvert medlem av mannskapet hennes visste det utmerket. Så tenkte hun, med et fjernt blikk i øynene, «Jeg oppkalte Nicholese etter en ikonisk skuespillerinne fra det 20. århundre. Jeg er glad jeg insisterte på at Starfleet skulle gjøre det til standard på alle skipene våre.»
Hun snudde seg tilbake til mannskapet. «Det er alt, offiserer. Du vet hva du skal gjøre!"
Vi vet ikke nøyaktig hva Uhura fortalte teamet hennes. Men JPayette og Rob Corlett hadde en ganske god idé. Her er Rob Corlett igjen:
Hvis den onde Catenati hører at de bruker denne strategien, kan han bytte navnene som vises på skjermen for å sikre at det er en syklus som er lengre enn 4.
For å bryte dette må fangene godta en hemmelig ordre som randomiserer sekvensen. De gjør dette ved å si noe sånt som "hvis du ser Uhuras navn, gå til knappen merket Chekov. Hvis du ser Chekovs navn vises, gå til knappen merket Smith, etc.
På denne måten spiller omorganiseringen av Catenati ingen rolle, siden det bare fungerer hvis du vet hvordan mannskapet vil svare på navnene på skjermene. De må imidlertid holde enhver ombestilling hemmelig, ellers kan den bli ødelagt igjen.
Som vi så, sørget Uhura for at hemmeligheten ble oppbevart. Hvert medlem av mannskapet trengte bare å bruke den samme hemmelige ordren og sikre at den onde Catenati ikke visste hva det var. Faktisk økte den endrede rekkefølgen til den onde Catenati faktisk mannskapets sannsynlighet for å lykkes!
Dette er hva som skjedde. Uhura var den første som ble tatt med til rulettkammeret. Hun trykket på tre knapper. Ingen var hennes. Skal hun være trist eller glad? Hun holdt pusten og trykket på den fjerde. Hun hadde funnet sin sanne knapp!
Hun visste at de alle kom til å bli reddet.
Puslespill 5
Hvilken grense nærmer den maksimale suksessprosenten seg når størrelsen på landingsfesten øker på ubestemt tid? Kan du forklare hvorfor denne metoden er så mye mer effektiv enn tilfeldig knappetrykk?
JPayette skrev:
Alt det ovennevnte generaliserer direkte til et mannskap på 2n medlemmene har maksimalt lov til å trykke n knapper. Fra puslespill 2 utleder vi at sjansen deres for å lykkes er
1 - (sum over k mellom n + 1 og 2n av 1/k).
Summen kan sammenlignes med integralet av 1/x over intervallet [n, 2n], som lar oss bevise at som n vokser til uendelig, reduseres sannsynligheten ovenfor for å konvergere til forbløffende 1 − ln(2) ≈ 30.6%. [Faktisk 30.69 % til to desimaler.]
Rob Corlett la til:
Hvis du ikke kjenner integrasjonen, kan du raskt få et omtrentlig svar ved å regne ut ved hjelp av et regneark. Jeg kom til 0.307 en gang n nådde ca. 750 som er nøyaktig med 3 desimaler.
Vi har allerede forklart ovenfor hvorfor denne metoden fungerer. Alle løkker lengre enn 1 deles av flere besetningsmedlemmer. Så deres suksesser og fiaskoer er sterkt korrelert. Det er en illustrasjon av prinsippet "Alle for en, og en for alle." Rett ut av Starfleet-manualen!
Takk til alle våre bidragsytere. JPayette og Rob Corlett leverte begge premieverdige svar som gjorde at denne løsningskolonnen virket nesten overflødig. Akk, jeg må holde meg til regelen vår om å velge én vinner per puslespillkolonne. Insights-prisen går til JPayette som en anerkjennelse for bidragene her og i forrige puslespill. Gratulerer! Rob Corlett, bidragene dine vil ikke bli glemt.
Vi sees neste måned for ny innsikt!
