Vår pusseluppgift förra månaden var att spara en Star Trek ytparti av åtta ledd av Företag Informatör Löjtnant Uhura (spelad av sen Nicole Nichols). Besättningen är fängslad av en utomjordisk ras, Catenati, på en planet i Halsband Nebula. För att komma undan måste de maximera sin sannolikhet att utföra en uppgift som till en början bara verkar erbjuda en dyster sannolikhet för framgång.
Besättningen på åtta informeras om uppgiften medan de tillfälligt hålls i ett gemensamt rum där de är fria att kommunicera och lägga strategier. Om några timmar kommer de att ledas, en i taget, till ett rum som kallas roulettekammaren. Detta rum har åtta knappar ordnade i rad, som var och en är programmerad att svara på en annan besättningsmedlem. För att vilseleda besättningen är varje knapp slumpmässigt felmärkt med en annan besättningsmedlems namn. Varje besättningsmedlem får trycka på upp till fyra av knapparna, i valfri ordning. När de trycker på en knapp kommer de att se vem knappen egentligen tillhör. Inom sina fyra försök måste de hitta knappen som tilldelats dem. För att besättningen ska gå fria måste alla lyckas med denna uppgift. Om ens en av dem misslyckas kommer alla att exekveras. Efter att en besättningsmedlem har slutfört sitt försök, ska de isoleras utan möjlighet att vidarebefordra information till någon av sina besättningskamrater.
Chanserna att lyckas verkar ringa. Om besättningsmedlemmar väljer knappar slumpmässigt kommer var och en att ha en chans på 1 på 2 att hitta sin knapp. Chansen att alla åtta lyckas är bara 1 på 256, eller cirka 0.4 %.
Men de behöver inte trycka på knappar slumpmässigt. Ett sätt att öka sannolikheten för framgång kan vara att jämna ut alla knapptryckningar på något sätt. Detta för oss till vår första pusselfråga.
Pussel 1
Hur mycket kan besättningens överlevnadssannolikhet förbättras om de ser till att varje knapp trycks in lika ofta (istället för att trycka på fyra knappar slumpmässigt)?
Rob Corlett och JPayette svarade bra på detta, liksom de gjorde alla andra frågor. När det gäller den svårfångade centrala idén bakom pusslen i denna kolumn, Rob Corlett, JPayette och Jouni Seppänen beskrev det vackert, medan Sacha Bugnon bidragit med en datorlösning.
Här är Rob Corletts svar:
Ett sätt att se till att varje knapp trycks in lika många gånger är att dela upp fångarna i två lika stora grupper om 4.
Varje grupp trycker bara på knapparna som motsvarar medlemmarna i deras grupp. Således, om A, B, C och D alla är i samma undergrupp, trycker de bara på knapparna för A, B, C och D.
Detta ändrar problemet till att fråga efter sannolikheten att varje fånge tilldelas rätt grupp eftersom de då garanterat kommer att trycka på sin knapp med fyra eller färre tryckningar.
Antalet sätt att befolka den första gruppen (och därför även den andra gruppen) med fyra personer är antalet sätt att välja 4 från 8 vilket är C(8, 4) = 70. Därför är det totala antalet sätt att att fördela alla i de två grupperna är 70.
Det finns bara en allokering som korrekt allokerar varje fånge till rätt grupp och så sannolikheten för att alla är i rätt grupp och att alla fångar överlever är 1/70 vilket är 3.66 gånger bättre än 1/256 i den tidigare strategin. [Men den är fortfarande väldigt liten: bara en chans på 1.4 %.]
Pussel 2
Det finns ett sätt att förbättra det ursprungliga dystra oddset mer än 90 gånger, till cirka 36.5 %, vilket verkar mirakulöst! Denna strategi innebär användning av slingor eller kedjor av gissningar - därav referenserna till halsbandsnebulosan och Catenati (kedja är latin för kedja). I grundformen av strategin börjar varje besättningsmedlem med att trycka på knappen som bär deras namn, går sedan vidare till knappen som bär namnet på den besättningsmedlem som den första knappen faktiskt tillhörde, och så vidare, skapar en kedja av namn.
Låt oss se hur detta fungerar i praktiken. I diagrammet visas knapparna med sina etiketter i vitt. De blå bokstäverna nedan visar knapparnas verkliga ägare. När den första besättningsmedlemmen, A, går in i roulettekammaren, trycker hon på knappen A först. Det här är C:s knapp, så hon trycker på knapp C nästa, sedan knapp E och slutligen knapp F, som faktiskt är A:s egen knapp, så hon har lyckats hitta den på fyra försök. Observera att knapparna ACEF bildar en sluten slinga av fyra knappar. När besättningsmedlemmarna C, E och F turas om kommer de också att gå runt samma slutna slinga, med utgångspunkt från sina egna respektive platser, och även hitta sina egna knappar i fyra försök.
Detta arrangemang har också två mindre öglor med två knappar vardera: BD och GH. Dessa fyra besättningsmedlemmar kommer att hitta sina egna knappar inom två försök. Så med detta arrangemang kommer alla besättningsmedlemmar att bli framgångsrika, och de kommer att ha förtjänat sin frihet. Det är klart att om arrangemanget bara innehåller slingor med längd 4 eller mindre kommer alla besättningsmedlemmar att bli framgångsrika och kommer att befrias. Om det å andra sidan finns en enda slinga på 5 eller fler, kommer alla besättningsmedlemmar på den slingan inte att hitta sin knapp på fyra försök, och besättningen kommer att avrättas. För att hitta sannolikheten för framgång kan vi hitta sannolikheten för att ha en slinga på 5, 6, 7 eller 8, lägga ihop dem och subtrahera summan från 1. Detta är lättare att beräkna än åt andra hållet eftersom för åtta knappar, kan det bara finnas en enda slinga med 5, 6, 7 eller 8 medlemmar.
Det finns 8! olika sätt att ordna åtta knappar. Men när vi gör loopar står samma loop för åtta av dessa arrangemang (ABCDEFGH bildar samma loop som BCDEFGHA, vilket är samma som CDEFGHAB, etc.). Så sannolikheten att ha en slinga med storlek 8 är (8!/8)/8!, vilket helt enkelt är 1/8. På liknande sätt är sannolikheten för att ha en slinga med storlek 7 1/7, storlek 6 är 1/6 och storlek 5 är 1/5. Därför är sannolikheten för framgång för vår orädda besättning 1 − (1/5 + 1/6 + 1/7 + 1/8), eller 36.5 %, som tidigare nämnts.
Ovanstående strategi fungerar för vilket antal fångar som helst, och förbättringen av oddsen jämfört med den slumpmässiga metoden ökar snabbt när det antalet ökar. Det är ungefär sju gånger för fyra fångar, 24 gånger för sex, 93 gånger för åtta och en häpnadsväckande (3.8 × 10)29)-faldig för 100 fångar. Nyckeln till att förstå denna enorma ökning är att metoden binder framgång eller misslyckande för varje medlem i gruppen till de andras. I mycket stor utsträckning lyckas eller misslyckas de alla tillsammans. Gruppens sannolikhet för framgång minskar inte alltför mycket från den för en enskild person, den sjunker endast från 50 % för en enskild fånge till 30.69 % när antalet fångar ökar utan gräns. Å andra sidan minskar sannolikheten för att ett slumpmässigt tillvägagångssätt eller till och med ett tillvägagångssätt med "jämna knapptryckningar" ska lyckas snabbt till mycket nära noll även för ett litet antal fångar.
Om logiken bakom denna strategi fortfarande verkar otydlig, här är en analys av problemet med 100 fångar i detta utmärkt video av Veritasium.
Pussel 3
Det här pusslet handlade om att löjtnant Uhura kom ihåg ett barndomsspel, som i princip var samma pussel, men för sex personer. Som en ledtråd föreslog jag att lösa problemet för fyra personer. Nu när vi har formeln kan vi enkelt beräkna sannolikheterna.
För fyra personer är sannolikheten att den längsta slingan bara är 2 eller 1: 1 − (1/3 + 1/4) eller 41.7 % med en sjufaldig vinst jämfört med slumpmässigt val.
För sex personer är sannolikheten att den längsta slingan är 3, 2 eller 1: 1 − (1/4 + 1/5 + 1/6) eller 38.3 % med mer än en 24-faldig vinst jämfört med slumpmässigt val.
Pussel 4
När vår berättelse fortsätter, visar det sig att en av Catenati har tagit en speciell motvilja mot Företag besättningen och övervakar dem på distans. Han misstänker att de har kommit på någon effektiv strategi baserad på Uhuras diagram. Han är fast besluten att omintetgöra deras plan genom att glida in i kammaren och medvetet ändra ordningen på knappetiketterna innan rouletten börjar. Kan han framgångsrikt omintetgöra planen? Vad måste den landande parten vara särskilt noga med att dölja?
Mycket tidigt i besättningens strategidiskussion fick Uhuras ögon plötsligt ihop sig. Hon gav en signal till sin besättning och hon gick över till att tala på Nicholese och tillkännagav: "All ytterligare diskussion på Nicholese, tack." Nicholese var ett nytt språk som Uhura hade uppfunnit tidigt i sin karriär för just denna typ av situation, för att kringgå användningen av universella översättare. "Du måste ha märkt den där misstänkta Catenati," fortsatte hon. "Han kunde försöka sabotera oss, så vi måste ändra vår plan. Här är vad vi behöver göra…”
Uhura beskrev den nya planen tills hon var övertygad om att varje medlem i hennes besättning kände till den mycket väl. Sedan funderade hon, med en avlägsen blick i ögonen, "Jag döpte Nicholese efter en ikonisk 20-talsskådespelerska. Jag är glad att jag insisterade på att Starfleet skulle göra det till standard på alla våra fartyg.”
Hon vände sig tillbaka till besättningen. "Det är allt, officerare. Du vet vad som ska göras!"
Vi vet inte exakt vad Uhura sa till sitt team. Men JPayette och Rob Corlett hade en ganska bra idé. Här är Rob Corlett igen:
Om den onde Catenati hör att de använder denna strategi kan han byta namn som visas på displayen för att säkerställa att det finns en cykel längre än 4.
För att bryta detta måste fångarna gå med på en hemlig beställning som randomiserar sekvensen. De gör detta genom att säga något i stil med "om du ser Uhuras namn, gå sedan till knappen märkt Chekov. Om du ser Chekovs namn visas, gå till knappen märkt Smith, etc.”
På så sätt spelar omordningen av Catenati ingen roll eftersom den bara fungerar om du vet hur besättningen kommer att svara på namnen på displayerna. De måste dock hålla eventuell omordning hemlig, annars kan den brytas igen.
Som vi såg såg Uhura till att hemligheten skulle förvaras säker. Varje medlem i besättningen behövde bara använda samma hemliga order och se till att den onda Catenati inte visste vad det var. Faktum är att den ändrade ordningen av den onde Catenati faktiskt ökade besättningens sannolikhet att lyckas!
Det här är vad som hände. Uhura var den första som togs till roulettekammaren. Hon tryckte på tre knappar. Ingen var hennes. Ska hon vara ledsen eller glad? Hon höll andan och tryckte på sin fjärde. Hon hade hittat sin riktiga knapp!
Hon visste att de alla skulle räddas.
Pussel 5
Vilken gräns närmar sig den maximala andelen framgång när storleken på landningssällskapet ökar på obestämd tid? Kan du förklara varför den här metoden är så mycket effektivare än slumpmässig knapptryckning?
JPayette skrev:
Allt ovanstående generaliserar direkt till en besättning på 2n medlemmar får som mest trycka n knappar. Från Pussel 2 drar vi slutsatsen att deras chans att lyckas är
1 - (summa över k mellan n +1 och 2n av 1 /k).
Summan kan jämföras med integralen av 1/x över intervallet [n, 2n], vilket tillåter oss att bevisa att som n växer till oändlighet, minskar sannolikheten ovan för att konvergera till häpnadsväckande 1 − ln(2) ≈ 30.6%. [Faktiskt 30.69 % till två decimaler.]
Rob Corlett lade till:
Om du inte kan integrationen kan du snabbt få ett ungefärligt svar genom beräkning med hjälp av ett kalkylblad. Jag kom till 0.307 en gång n nådde cirka 750 vilket är exakt med 3 decimaler.
Vi har redan förklarat ovan varför denna metod fungerar. Alla loopar längre än 1 delas av flera besättningsmedlemmar. Så deras framgångar och misslyckanden är starkt korrelerade. Det är en illustration av principen "Alla för en och en för alla." Direkt ur Starfleet-manualen!
Tack till alla våra bidragsgivare. JPayette och Rob Corlett lämnade båda in prisvärda svar som gjorde att denna lösningskolumn nästan verkade överflödig. Tyvärr, jag måste hålla fast vid vår regel att utse en vinnare per pusselkolumn. Insights-priset går till JPayette som ett erkännande av bidragen här och i det föregående pusslet. Grattis! Rob Corlett, dina bidrag kommer inte att glömmas bort.
Vi ses nästa månad för nya insikter!
