Onze puzzel taak vorige maand was om een te redden Star Trek oppervlakte partij van acht onder leiding van de Enterprise Communicatiemedewerker Luitenant Uhura (gespeeld door de late) Nichelle Nichols). De bemanning wordt gevangengenomen door een buitenaards ras, de Catenati, op een planeet in de Ketting Nevel. Om te ontsnappen, moeten ze hun kans op het uitvoeren van een taak die op het eerste gezicht slechts een sombere kans op succes biedt, zo groot mogelijk maken.
De achtkoppige bemanning wordt op de hoogte gehouden van de taak terwijl ze tijdelijk worden vastgehouden in een gemeenschappelijke ruimte waar ze vrij zijn om te communiceren en strategieën te bedenken. Over een paar uur worden ze één voor één naar een kamer geleid die de roulettekamer wordt genoemd. Deze kamer heeft acht op een rij gerangschikte knoppen, die elk zijn geprogrammeerd om op een ander bemanningslid te reageren. Om de bemanning te misleiden, is elke knop willekeurig verkeerd gelabeld met de naam van een ander bemanningslid. Elk bemanningslid mag maximaal vier van de knoppen indrukken, in willekeurige volgorde. Telkens wanneer ze op een knop drukken, zien ze van wie de knop echt is. Binnen hun vier pogingen moeten ze de knop vinden die aan hen is toegewezen. Om de bemanning vrij te laten gaan, moeten ze allemaal slagen in deze taak. Als er ook maar één faalt, worden ze allemaal uitgevoerd. Nadat een bemanningslid zijn poging heeft voltooid, moeten ze worden geïsoleerd zonder enige manier om informatie door te geven aan een van hun bemanningsleden.
De kans op succes lijkt miniem. Als bemanningsleden willekeurig knoppen kiezen, heeft elk een kans van 1 op 2 om hun knop te vinden. De kans dat ze alle acht slagen is slechts 1 op 256, of ongeveer 0.4%.
Maar ze hoeven niet willekeurig op knoppen te drukken. Een manier om de kans op succes te vergroten, zou kunnen zijn om alle druk op de knop op de een of andere manier gelijk te maken. Dit brengt ons bij onze eerste puzzelvraag.
Puzzel 1
Met hoeveel kan de overlevingskans van de bemanning worden verbeterd als ze ervoor zorgen dat elke knop even vaak wordt ingedrukt (in plaats van willekeurig op vier knoppen te drukken)?
Rob Corlett en JPayette beantwoordden dit goed, net als alle andere vragen. Wat betreft het ongrijpbare centrale idee achter de puzzels in deze kolom, Rob Corlett, JPayette en Jouni Seppanen beschreef het prachtig, terwijl Sacha Bugnon een computeroplossing bijgedragen.
Hier is het antwoord van Rob Corlett:
Een manier om ervoor te zorgen dat elke knop een gelijk aantal keren wordt ingedrukt, is door de gevangenen in twee even grote groepen van 4 te verdelen.
Elke groep drukt alleen op de knoppen die overeenkomen met de leden van hun groep. Dus als A, B, C en D allemaal in dezelfde subgroep zitten, drukken ze alleen op de knoppen voor A, B, C en D.
Dit verandert het probleem in het vragen naar de kans dat elke gevangene aan de juiste groep wordt toegewezen, aangezien ze dan gegarandeerd vier keer of minder op hun knop drukken.
Het aantal manieren om de eerste groep (en dus ook de tweede groep) met vier personen te vullen, is het aantal manieren om 4 te kiezen uit 8, wat C (8, 4) = 70 is. Daarom is het totale aantal manieren van het toewijzen van iedereen in de twee groepen is 70.
Er is maar één toewijzing die elke gevangene correct aan de juiste groep toewijst en dus is de kans dat iedereen in de juiste groep zit en alle gevangenen overleven 1/70, wat 3.66 keer beter is dan de 1/256 van de vorige strategie. [Maar het is nog steeds erg klein: slechts 1.4% kans.]
Puzzel 2
Er is een manier om de oorspronkelijke sombere kansen 90-voudig te verbeteren, tot ongeveer 36.5%, wat wonderbaarlijk lijkt! Deze strategie omvat het gebruik van lussen of kettingen van gissingen - vandaar de verwijzingen naar de Halskettingnevel en de Catenati (keten is Latijn voor ketting). In de basisvorm van de strategie begint elk bemanningslid door op de knop met hun naam te drukken, gaat dan door naar de knop met de naam van het bemanningslid waartoe de eerste knop werkelijk behoorde, enzovoort, waardoor een reeks namen ontstaat.
Laten we eens kijken hoe dit in de praktijk werkt. In het diagram worden de knoppen weergegeven met hun labels in het wit. De blauwe letters hieronder tonen de echte eigenaren van de knoppen. Wanneer het eerste bemanningslid, A, de roulettekamer binnenkomt, drukt ze eerst op knop A. Dit is de knop van C, dus ze drukt vervolgens op knop C, vervolgens op knop E en ten slotte op knop F, wat in feite A's eigen knop is, dus ze heeft deze in vier pogingen gevonden. Merk op dat de knoppen ACEF een gesloten lus van vier knoppen vormen. Wanneer bemanningsleden C, E en F aan de beurt zijn, zullen ze ook rond dezelfde gesloten lus gaan, beginnend vanaf hun eigen respectievelijke plaatsen, en ook hun eigen knoppen vinden in vier pogingen.
Deze opstelling heeft ook twee kleinere lussen van elk twee knoppen: BD en GH. Deze vier bemanningsleden zullen binnen twee pogingen hun eigen knoppen vinden. Dus met deze regeling zullen alle bemanningsleden succesvol zijn en hebben ze hun vrijheid verdiend. Het is duidelijk dat als de opstelling alleen maar lussen van 4 of minder bevat, alle bemanningsleden succesvol zullen zijn en worden bevrijd. Als er daarentegen een enkele lus is van 5 of meer, dan zullen alle bemanningsleden op die lus hun knop niet kunnen vinden in vier pogingen en zal de bemanning worden geëxecuteerd. Om de kans op succes te vinden, kunnen we de kans op een lus van 5, 6, 7 of 8 vinden, deze optellen en die som van 1 aftrekken. Dit is gemakkelijker te berekenen dan andersom, want voor acht knoppen, kan er slechts een enkele lus zijn met 5, 6, 7 of 8 leden.
Er zijn er 8! verschillende manieren om acht knoppen te rangschikken. Maar wanneer we lussen maken, is dezelfde lus verantwoordelijk voor acht van deze arrangementen (ABCDEFGH vormt dezelfde lus als BCDEFGHA, wat hetzelfde is als CDEFGHAB, enz.). Dus de kans op een lus van maat 8 is (8!/8)/8!, wat simpelweg 1/8 is. Evenzo is de kans op een lus van maat 7 1/7, van maat 6 is 1/6 en van maat 5 is 1/5. Daarom is de kans op succes voor onze onverschrokken bemanning 1 − (1/5 + 1/6 + 1/7 + 1/8), of 36.5%, zoals eerder vermeld.
De bovenstaande strategie werkt voor een willekeurig aantal gevangenen, en de verbetering van de kansen ten opzichte van de willekeurige benadering neemt snel toe naarmate dat aantal toeneemt. Het is ongeveer zeven keer voor vier gevangenen, 24 keer voor zes, 93 keer voor acht en een verbazingwekkende (3.8 x 1029)-vouw voor 100 gevangenen. De sleutel tot het begrijpen van deze enorme toename is dat de methode het succes of falen van elk lid van de groep koppelt aan dat van de anderen. In zeer grote mate slagen ze of falen ze allemaal samen. De kans op succes van de groep daalt niet veel van die van een enkele persoon, van slechts 50% voor een enkele gevangene tot 30.69% omdat het aantal gevangenen onbeperkt wordt verhoogd. Aan de andere kant neemt de kans dat een willekeurige benadering of zelfs een "even-knop indrukken"-benadering slaagt, snel af tot zeer dicht bij nul voor zelfs een klein aantal gevangenen.
Als de logica achter deze strategie nog steeds vaag lijkt, is hier een analyse van het probleem van 100 gevangenen hierin uitstekende video van Veritasium.
Puzzel 3
Deze puzzel ging over luitenant Uhura die zich een kinderspel herinnerde, dat in wezen dezelfde puzzel was, maar voor zes personen. Als hint stelde ik voor om het probleem voor vier personen uit te werken. Nu we de formule hebben, kunnen we de kansen eenvoudig berekenen.
Voor vier personen is de kans dat de langste lus slechts 2 of 1 is: 1 − (1/3 + 1/4) of 41.7% met een zevenvoudige winst ten opzichte van willekeurige keuze.
Voor zes personen is de kans dat de langste lus 3, 2 of 1 is: 1 − (1/4 + 1/5 + 1/6) of 38.3% met meer dan een 24-voudige winst ten opzichte van willekeurige keuze.
Puzzel 4
Naarmate ons verhaal verder gaat, blijkt dat een van de Catenati een speciale hekel heeft aan de Enterprise bemanning en houdt ze op afstand in de gaten. Hij vermoedt dat ze een effectieve strategie hebben bedacht op basis van het diagram van Uhura. Hij is vastbesloten om hun plan te verijdelen door de kamer binnen te glippen en opzettelijk de volgorde van de knoplabels te veranderen voordat het roulette begint. Kan hij het plan met succes dwarsbomen? Waarop moet de landingspartij vooral letten om te verbergen?
Heel vroeg in de strategiebespreking van de bemanning vernauwden Uhura's ogen zich plotseling. Ze gaf een signaal aan haar bemanning en ze schakelde over op het spreken in het Nicholees en kondigde aan: "Alle verdere discussie in het Nicholees, alstublieft." Nicholees was een nieuwe taal die Uhura vroeg in haar carrière had uitgevonden voor precies dit soort situaties, om het gebruik van universele vertalers te omzeilen. 'Je moet die verdachte Catenati hebben opgemerkt,' vervolgde ze. “Hij zou kunnen proberen ons te saboteren, dus we moeten ons plan aanpassen. Dit is wat we moeten doen…”
Uhura schetste het nieuwe plan totdat ze ervan overtuigd was dat elk lid van haar bemanning het heel goed kende. Toen mijmerde ze, met een verre blik in haar ogen: 'Ik heb Nicholese genoemd naar een iconische actrice uit de 20e eeuw. Ik ben blij dat ik erop heb aangedrongen dat Starfleet het standaard zou maken op al onze schepen.”
Ze wendde zich weer tot de bemanning. 'Dat is alles, agenten. Je weet wat je moet doen!"
We weten niet precies wat Uhura haar team heeft verteld. Maar JPayette en Rob Corlett hadden een redelijk goed idee. Hier is Rob Corlett weer:
Als de gemene Catenati hoort dat ze deze strategie toepassen, kan hij de namen die op het display worden weergegeven omwisselen om ervoor te zorgen dat er een cyclus is die langer is dan 4.
Om dit te doorbreken, moeten de gevangenen akkoord gaan met een geheime volgorde die de volgorde willekeurig maakt. Ze doen dit door iets te zeggen als 'als je Uhura's naam ziet, ga dan naar de knop met de markering Chekov. Als je de naam van Chekov ziet, ga dan naar de knop met de aanduiding Smith, enz.”
Op deze manier maakt het opnieuw ordenen door de Catenati niet uit, het werkt alleen als je weet hoe de bemanning zal reageren op de namen op de displays. Ze moeten elke herschikking echter geheim houden, anders kan het opnieuw worden verbroken.
Zoals we zagen, zorgde Uhura ervoor dat het geheim veilig zou worden bewaard. Elk lid van de bemanning moest gewoon dezelfde geheime volgorde gebruiken en ervoor zorgen dat de kwaadaardige Catenati niet wist wat het was. De veranderde volgorde door de kwaadaardige Catenati verhoogde zelfs de kans op slagen van de bemanning!
Dit is wat er gebeurde. Uhura was de eerste die naar de roulettekamer werd gebracht. Ze drukte op drie knoppen. Geen enkele was van haar. Moet ze verdrietig of blij zijn? Ze hield haar adem in en drukte op haar vierde. Ze had haar ware knop gevonden!
Ze wist dat ze allemaal gered zouden worden.
Puzzel 5
Welke grens nadert het maximale succespercentage als de omvang van de landingspartij oneindig toeneemt? Kun je uitleggen waarom deze methode zoveel efficiënter is dan het willekeurig indrukken van een knop?
JPayette schreef:
Al het bovenstaande generaliseert eenvoudig naar een bemanning van 2n leden mogen elk maximaal drukken n toetsen. Uit puzzel 2 leiden we af dat hun kans op succes is
1 − (som over k tussen n + 1 en 2n van 1/k).
De som kan worden vergeleken met de integraal van 1/x in de tussentijd [n, 2n], waarmee we kunnen bewijzen dat als n groeit tot oneindig, neemt de bovenstaande kans af om te convergeren naar een verbazingwekkende 1 − ln(2) ≈ 30.6%. [Eigenlijk 30.69% tot twee cijfers achter de komma.]
Rob Corlett voegde toe:
Als u de integratie niet kent, kunt u snel tot een benaderend antwoord komen door berekening met behulp van een spreadsheet. Ik ben een keer op 0.307 gekomen n bereikte ongeveer 750 wat tot op 3 decimalen nauwkeurig is.
We hebben hierboven al uitgelegd waarom deze methode werkt. Alle lussen langer dan 1 worden gedeeld door meerdere bemanningsleden. Hun successen en mislukkingen zijn dus sterk gecorreleerd. Het is een illustratie van het principe "Allen voor één en één voor allen". Rechtstreeks uit de Starfleet-handleiding!
Bedankt aan al onze bijdragers. JPayette en Rob Corlett hebben beide waardevolle antwoorden ingediend waardoor deze kolom met oplossingen bijna overbodig leek. Helaas moet ik me houden aan onze regel om één winnaar per puzzelkolom te kiezen. De Insights-prijs gaat naar JPayette als erkenning voor bijdragen hier en in de vorige puzzel. Gefeliciteerd! Rob Corlett, uw bijdragen zullen niet vergeten worden.
Tot volgende maand voor nieuwe inzichten!
