Probleem met gevangenen en petten, waarvan de kleur moet worden bepaald
Recreatie / / December 31, 2020
Het sluitsysteem ziet alle doppen, maar kan alleen "zwart" of "wit" zeggen, terwijl het tegelijkertijd iedereen op de hoogte stelt van de verborgen informatie. De gevangenen weten het totale aantal zwarte en witte petten niet, er zijn meer dan twee mogelijke opties. Maar ze zijn beperkt tot slechts twee versies als het gaat om het concept van pariteit: het aantal kan even of oneven zijn.
De sleutel tot het oplossen van het probleem is dit: de gevangenen zijn het erover eens dat de eerstehulpverlener bijvoorbeeld "zwart" zal zeggen, als hij een oneven aantal zwarte kappen vooraan ziet, en "wit" als hij een even aantal zwarte kappen ziet caps.
Laten we eens kijken naar het voorbeeld uit de bovenstaande afbeelding. De langste gevangene # 1 ziet drie zwarte petten voor zich. Hij zegt hardop "zwart". Dit geeft alle anderen de informatie dat er een oneven aantal zwarte kappen voor ons ligt. De eerste gevangene heeft een fout gemaakt met de kleur van zijn pet, maar dat is oké: als je eenmaal verkeerd mag antwoorden.
Gevangene # 2 ziet een oneven aantal zwarte petten voor haar. Ze realiseert zich dat ze blank is en antwoordt correct. Gevangene # 3 ziet een even aantal zwarte petten en vermoedt dat hij een zwarte pet draagt die de eerste twee gevangenen hebben gezien.
Gevangene nr. 4 hoort het antwoord en realiseert zich dat ze moet zoeken naar een even aantal zwarte petten, omdat er een zwarte achter haar rug zat, maar ze ziet er maar één voor zich en concludeert dat haar pet zwart is. Gevangenen nr. 5-9 zijn op zoek naar een oneven aantal zwarte petten, die ze gewoon zien, terwijl ze beseffen dat ze witte petten dragen. De beurt komt bij de tiende gevangene. Als gevangene # 9 een oneven aantal zwarte petten heeft gezien, betekent dit maar één ding: gevangene # 10 heeft een zwarte pet.
Dit is hoe dit algoritme zou werken voor elke set wieldoppen. Voor de eerste deelnemer is de kans op een onjuist antwoord 50%, maar de informatie over even-oneven pariteit, die hij zal geven, stelt de rest van de gevangenen in staat de kleur van hun pet te raden.
Elke respondent begint het aantal even en oneven caps te evalueren. Als het in zijn hoofd berekende aantal niet overeenkomt met wat hij ziet, dan heeft zijn pet dezelfde kleur. Elke keer in dit geval houdt de volgende responder er rekening mee dat de even onevenheid van de resterende caps nu is veranderd.
Deze puzzel is een vertaling van een TED-Ed-video.