Honderd gevangenen en een gloeilamp

Honderd gevangenen en een gloeilamp
Hans van Ditmarsch & Barteld Kooi
[email protected] & [email protected]
Vakantiecursus Wiskunde 2014 — Nieuwe Tijden
Honderd gevangenen en een gloeilamp
Honderd gevangenen, gezamenlijk in de gevangeniskantine, wordt
medegedeeld dat ze in isolatiecellen geplaatst zullen worden en
daarna ´e´en voor ´e´en ondervraagd, in een kamer met een lamp met
een aan-uitschakelaar. De gevangenen kunnen (alleen) met elkaar
communiceren door de lamp aan of uit te doen. De lamp is aan
het begin uit. Er is geen vaste volgorde van ondervraging, er is
geen standaard tijdsduur tussen de ondervragingen, en dezelfde
gevangene kan meerdere keren achter elkaar ondervraagd worden.
Op ieder moment zal iedere gevangene ooit nog eens ondervraagd
worden. Als een gevangene ondervraagd wordt, kan deze: niets
doen, de lamp uitdoen, de lamp aandoen, of verklaren dat iedereen
ondervraagd is. Als dit waar is, worden alle gevangenen vrijgelaten.
Anders worden ze opgehangen. Kunnen de gevangenen, zolang ze
nog bij elkaar zijn in de kantine en niet naar de isolatiecellen
gebracht zijn, een protocol overeenkomen waardoor ze vrijgelaten
worden?
Honderd gevangenen — wel of geen oplossing?
Stel er is ´e´en gevangene.
Honderd gevangenen — wel of geen oplossing?
Stel er is ´e´en gevangene.
Protocol:
Als je ondervraagd wordt, zeg dan dat iedereen ondervraagd is.
Honderd gevangenen — wel of geen oplossing?
Stel er is ´e´en gevangene.
Protocol:
Als je ondervraagd wordt, zeg dan dat iedereen ondervraagd is.
Stel er zijn twee gevangenen.
Honderd gevangenen — wel of geen oplossing?
Stel er is ´e´en gevangene.
Protocol:
Als je ondervraagd wordt, zeg dan dat iedereen ondervraagd is.
Stel er zijn twee gevangenen.
Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt, en
de lamp is aan maar jij hebt hem niet aangedaan, zeg dan dat
iedereen ondervraagd is.
Honderd gevangenen — wel of geen oplossing?
Stel er is ´e´en gevangene.
Protocol:
Als je ondervraagd wordt, zeg dan dat iedereen ondervraagd is.
Stel er zijn twee gevangenen.
Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt, en
de lamp is aan maar jij hebt hem niet aangedaan, zeg dan dat
iedereen ondervraagd is.
Stel er zijn drie gevangenen . . .
Honderd gevangenen — E´en, twee, drie, veel
Wat allemaal niet lukt.
I
Voelen of de lamp nog warm is. Heeft geen zin.
I
De lamp stukslaan. Beter van niet. Lukt voor drie
gevangenen, maar je bereikt de 100 niet.
I
Bijhouden hoe lang de ondervragingen duren. Heeft geen zin.
I
De gevangenen kunnen in de isoleercellen zien of de lamp aan
of uit is. Nee!
I
De gevangenen kunnen in de isoleercellen horen of de
schakelaar overgehaald wordt. Nee!
I
Er is een geheime verbinding tussen de isolatiecellen en de
ondervragingsruimte. Nee!
Honderd gevangenen — Stel er zijn drie gevangenen
GEEN Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt en
de lamp is aan maar jij hebt hem niet aangedaan, doe hem dan uit.
Houd bij hoe vaak je dat doet. Als je de lamp twee keer hebt
uitgedaan, en je wordt opnieuw ondervraagd en de lamp is aan, zeg
dan dat alle drie gevangenen ondervraagd zijn.
Honderd gevangenen — Stel er zijn drie gevangenen
GEEN Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt en
de lamp is aan maar jij hebt hem niet aangedaan, doe hem dan uit.
Houd bij hoe vaak je dat doet. Als je de lamp twee keer hebt
uitgedaan, en je wordt opnieuw ondervraagd en de lamp is aan, zeg
dan dat alle drie gevangenen ondervraagd zijn.
Bovenindex: toestand van de lamp.
Onderindex: hoe vaak de voorgaande gevangene heeft uitgedaan.
0
Anna10 Bob01 Bob11 Anna01 Caro10 Anna02
Honderd gevangenen — Stel er zijn drie gevangenen
GEEN Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt en
de lamp is aan maar jij hebt hem niet aangedaan, doe hem dan uit.
Houd bij hoe vaak je dat doet. Als je de lamp twee keer hebt
uitgedaan, en je wordt opnieuw ondervraagd en de lamp is aan, zeg
dan dat alle drie gevangenen ondervraagd zijn.
Bovenindex: toestand van de lamp.
Onderindex: hoe vaak de voorgaande gevangene heeft uitgedaan.
0
Dit gaat goed.
Anna10 Bob01 Bob11 Anna01 Caro10 Anna02
Honderd gevangenen — Stel er zijn drie gevangenen
GEEN Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt en
de lamp is aan maar jij hebt hem niet aangedaan, doe hem dan uit.
Houd bij hoe vaak je dat doet. Als je de lamp twee keer hebt
uitgedaan, en je wordt opnieuw ondervraagd en de lamp is aan, zeg
dan dat alle drie gevangenen ondervraagd zijn.
Bovenindex: toestand van de lamp.
Onderindex: hoe vaak de voorgaande gevangene heeft uitgedaan.
0
Anna10 Bob01 Bob11 Anna01 Caro10 Anna02
Dit gaat goed.
0
Anna10 Bob01 Bob11 Caro01 Caro11 Anna01
Honderd gevangenen — Stel er zijn drie gevangenen
GEEN Protocol:
Als je ondervraagd wordt en de lamp is uit, doe hem dan aan; als
je ondervraagd wordt, en jij hebt de lamp eerder aangedaan en de
lamp is nog steeds aan, doe dan niets; als je ondervraagd wordt en
de lamp is aan maar jij hebt hem niet aangedaan, doe hem dan uit.
Houd bij hoe vaak je dat doet. Als je de lamp twee keer hebt
uitgedaan, en je wordt opnieuw ondervraagd en de lamp is aan, zeg
dan dat alle drie gevangenen ondervraagd zijn.
Bovenindex: toestand van de lamp.
Onderindex: hoe vaak de voorgaande gevangene heeft uitgedaan.
0
Anna10 Bob01 Bob11 Anna01 Caro10 Anna02
Dit gaat goed.
0
Anna10 Bob01 Bob11 Caro01 Caro11 Anna01
Dit gaat fout. Niemand bereikt ooit 2.
Honderd gevangenen en een gloeilamp — de oplossing
Gevangenen kunnen verschillende rollen vervullen in het protocol!
Honderd gevangenen en een gloeilamp — de oplossing
Gevangenen kunnen verschillende rollen vervullen in het protocol!
Protocol: De gevangenen wijzen onder elkaar een teller aan. Voor
de teller geldt: Als je ondervraagd wordt en de lamp is uit doe dan
niets; als je ondervraagd wordt en de lamp is aan, doe hem dan uit
- houdt bij hoe vaak je dat doet; als je de lamp 99 keer hebt
uitgedaan, verklaar dan dat alle 100 gevangenen ondervraagd zijn.
Voor de overige gevangenen (volgers) geldt: Als je ondervraagd
wordt en de lamp is uit en je hebt hem nog niet eerder aangedaan,
doe hem dan aan; als je ondervraagd wordt en de lamp is uit en je
hebt hem al eerder aangedaan, doe dan niets; als je ondervraagd
wordt en de lamp is aan, doe dan niets.
Drie uitvoeringen van het protocol:
— 0 Bob1 Anna01 Caro1 Anna02
— 0 Anna0 Bob1 Caro1 Anna01 Bob0 Anna01 Caro1 Caro1 Bob1 Bob1 Anna02
— 0 Bob1 Anna01 Bob0 Caro1 Bob1 Anna02
Honderd gevangenen en een gloeilamp — de oplossing
Protocol: De gevangenen wijzen onder elkaar een teller aan. Voor
de teller geldt: Als je ondervraagd wordt en de lamp is uit doe dan
niets; als je ondervraagd wordt en de lamp is aan, doe hem dan uit
- houdt bij hoe vaak je dat doet; als je de lamp 99 keer hebt
uitgedaan, verklaar dan dat alle 100 gevangenen ondervraagd zijn.
Voor de overige gevangenen (volgers) geldt: Als je ondervraagd
wordt en de lamp is uit en je hebt hem nog niet eerder aangedaan,
doe hem dan aan; als je ondervraagd wordt en de lamp is uit en je
hebt hem al eerder aangedaan, doe dan niets; als je ondervraagd
wordt en de lamp is aan, doe dan niets.
Het protocol termineert als de verroostering van ondervragingen
eerlijk (‘fair’) is. Daarom stond in de beschrijving van het raadsel:
Op ieder moment zal iedere gevangene ooit nog eens ondervraagd
worden.
Honderd gevangenen en een gloeilamp — de oplossing
Protocol: De gevangenen wijzen onder elkaar een teller aan. Voor
de teller geldt: Als je ondervraagd wordt en de lamp is uit doe dan
niets; als je ondervraagd wordt en de lamp is aan, doe hem dan uit
- houdt bij hoe vaak je dat doet; als je de lamp 99 keer hebt
uitgedaan, verklaar dan dat alle 100 gevangenen ondervraagd zijn.
Voor de overige gevangenen (volgers) geldt: Als je ondervraagd
wordt en de lamp is uit en je hebt hem nog niet eerder aangedaan,
doe hem dan aan; als je ondervraagd wordt en de lamp is uit en je
hebt hem al eerder aangedaan, doe dan niets; als je ondervraagd
wordt en de lamp is aan, doe dan niets.
Het protocol termineert als de verroostering van ondervragingen
eerlijk (‘fair’) is. Daarom stond in de beschrijving van het raadsel:
Op ieder moment zal iedere gevangene ooit nog eens ondervraagd
worden.
De volgende uitvoering is oneerlijk: 0, 1, 2, . . . , 98, 99, 0, 1, 0, 1, . . .
Honderd gevangenen — Is het licht eerst aan of uit?
Stel dat niet bekend is of het licht in eerste instantie aan of uit is.
Wat is dan een protocol om het probleem op te lossen?
1. Als de teller net zo vaak telt als hiervoor, dan zegt de teller
ten onrechte dat iedereen ondervraagd is als het licht aan het
begin aan was.
1
Anna01 Caro1 Anna02 Bob1 Anna03
2. Als de teller ´e´en meer telt, dan termineert het protocol niet
als het licht aan het begin uit was.
0
Bob1 Anna01 Caro1 Anna02 Bob0 Anna02
Honderd gevangenen — Is het licht eerst aan of uit?
Protocol: De gevangenen wijzen onder elkaar een teller aan. Voor
de teller geldt: Als je ondervraagd wordt en de lamp is uit doe dan
niets; als je ondervraagd wordt en de lamp is aan, doe hem dan uit
— houd bij hoe vaak je dat doet; als je de lamp 198 keer hebt
uitgedaan, verklaar dan dat alle n gevangenen ondervraagd zijn.
Voor de overige gevangenen (volgers) geldt: Als je ondervraagd
wordt en de lamp is uit en je hebt hem nog niet twee keer
aangedaan, doe hem dan aan; als je ondervraagd wordt en de lamp
is uit en je hebt hem al twee keer eerder aangedaan, doe dan niets;
als je ondervraagd wordt en de lamp is aan, doe dan niets.
Honderd gevangenen — Is het licht eerst aan of uit?
Protocol: De gevangenen wijzen onder elkaar een teller aan. Voor
de teller geldt: Als je ondervraagd wordt en de lamp is uit doe dan
niets; als je ondervraagd wordt en de lamp is aan, doe hem dan uit
— houd bij hoe vaak je dat doet; als je de lamp 198 keer hebt
uitgedaan, verklaar dan dat alle n gevangenen ondervraagd zijn.
Voor de overige gevangenen (volgers) geldt: Als je ondervraagd
wordt en de lamp is uit en je hebt hem nog niet twee keer
aangedaan, doe hem dan aan; als je ondervraagd wordt en de lamp
is uit en je hebt hem al twee keer eerder aangedaan, doe dan niets;
als je ondervraagd wordt en de lamp is aan, doe dan niets.
Er twee manieren om 198 keer het licht uitgedaan te hebben.
I
Het licht was uit en 99 volgers hebben twee keer het licht
aangedaan.
I
Het licht was aan en 98 volgers hebben twee keer het licht
aangedaan en 1 volger ´e´en keer.
In beide gevallen zijn alle gevangenen ondervraagd.
Hoe een volger de teller kan helpen
Alleen in de eerste uitvoering weet Anna voor Bob en Caroline:
— 0 Bob1 Anna01 Caro1 Anna02
— 0 Anna00 Bob1 Caro1 Anna01 Bob0 Anna01 Caro1 Caro1 Bob1 Bob1 Anna02
— 0 Bob1 Anna01 Bob0 Caro1 Bob1 Anna02
Hoe een volger de teller kan helpen
Alleen in de eerste uitvoering weet Anna voor Bob en Caroline:
— 0 Bob1 Anna01 Caro1 Anna02
— 0 Anna00 Bob1 Caro1 Anna01 Bob0 Anna01 Caro1 Caro1 Bob1 Bob1 Anna02
— 0 Bob1 Anna01 Bob0 Caro1 Bob1 Anna02
Volgers houden bij hoe vaak ze de lamp van uit aan zien gaan.
Als zodanig geldt:
I
Bij je eerste ondervraging is het licht aan.
I
De eerste keer dat je het licht uit ziet, doe je het aan.
I
Na een volgende keer dat je het licht uit ziet, zie je nog weer
later dat het aan is.
Protocol: De teller en de volgers voeren het ‘standaard’ protocol
uit. Maar de volgers houden tevens bij hoe vaak ze de lamp van
uit aan zien gaan. Als een volger dit n − 1 keer gezien heeft, zegt
deze dat iedereen ondervraagd is.
Hoe een volger de teller kan helpen
Alleen in de eerste uitvoering weet Anna voor Bob en Caroline:
— 0 Bob11 Anna01 Caro11 Anna02
— 0 Anna00 Bob11 Caro11 Anna01 Bob01 Anna01 Caro12 Caro1 Bob1 Bob1 Anna02
— 0 Bob11 Anna01 Bob01 Caro1 Bob12 Anna02
Volgers houden bij hoe vaak ze de lamp van uit aan zien gaan.
Als zodanig geldt:
I
Bij je eerste ondervraging is het licht aan.
I
De eerste keer dat je het licht uit ziet, doe je het aan.
I
Na een volgende keer dat je het licht uit ziet, zie je nog weer
later dat het aan is.
Protocol: De teller en de volgers voeren het ‘standaard’ protocol
uit. Maar de volgers houden tevens bij hoe vaak ze de lamp van
uit aan zien gaan. Als een volger dit n − 1 keer gezien heeft, zegt
deze dat iedereen ondervraagd is.
Hoe een volger de teller kan helpen
Protocol: De teller en de volgers voeren het ‘standaard’ protocol
uit. Maar de volgers houden tevens bij hoe vaak ze de lamp van
uit aan zien gaan. Als een volger dit n − 1 keer gezien heeft, zegt
deze dat iedereen ondervraagd is.
Hoe waarschijnlijk is het dat een volger verklaart dat het licht uit is
voor de teller?
Hoe een volger de teller kan helpen
Protocol: De teller en de volgers voeren het ‘standaard’ protocol
uit. Maar de volgers houden tevens bij hoe vaak ze de lamp van
uit aan zien gaan. Als een volger dit n − 1 keer gezien heeft, zegt
deze dat iedereen ondervraagd is.
Hoe waarschijnlijk is het dat een volger verklaart dat het licht uit is
voor de teller?
I
Als er n = 3 gevangenen zijn, evenveel kans.
I
Als er n = 100 gevangenen zijn, minder dan 5,63 · 10−72 .
Een probabilistisch protocol — iedereen dezelfde rol!
Deze gaat even in het Engels. Ik piekerde me suf over de juiste en
inzichtelijke vertaling...
The original riddle can be seen as 100 prisoners each carrying a
token worth one point. A prisoner turning the light on if he hasn’t
done that before drops his point. The counter turning it off
collects a point and adds it to his token. The protocol continues
until the counter has collected 100 points.
Maar uiteraard kan iedereen zijn ‘token’ verhogen en verlagen!
Zolang niet iedereen altijd teller (‘collecting’) of volger (‘dropping’)
blijft. Dit is de basis voor een probabilistisch protocol.
Een probabilistisch protocol — iedereen dezelfde rol!
Each prisoner holds a token initially worth one point. Turning the
light on if it is off, means dropping one point. Leaving the light on
if it is on, means not being able to drop one point. Turning the
light off if it is on, means collecting one point. Leaving the light
off if it is off, means not being able to collect one point.
Protocol: Let your token be m points. If the light is on, add one.
Let a function Pr : {0, ..., n} → [0, 1] be given, with
Pr (0) = Pr (1) = 1, 0 < Pr (x) < 1 for x 6= 0, 1, n, and Pr (n) = 0.
Drop your point with probability Pr (m), otherwise, collect it. The
protocol terminates once a prisoner has collected n points.
Een probabilistisch protocol — iedereen dezelfde rol!
Each prisoner holds a token initially worth one point. Turning the
light on if it is off, means dropping one point. Leaving the light on
if it is on, means not being able to drop one point. Turning the
light off if it is on, means collecting one point. Leaving the light
off if it is off, means not being able to collect one point.
Protocol: Let your token be m points. If the light is on, add one.
Let a function Pr : {0, ..., n} → [0, 1] be given, with
Pr (0) = Pr (1) = 1, 0 < Pr (x) < 1 for x 6= 0, 1, n, and Pr (n) = 0.
Drop your point with probability Pr (m), otherwise, collect it. The
protocol terminates once a prisoner has collected n points.
Pr (0) = Pr (1) = 1, Pr (2) = 0.5, Pr (3) = Pr (4) = 0. Lower index:
the number of points plus the state of the light. Upper index: state
of the light. Bold: prisoner collects point. Not bold: drops point.
0
Anna11 Bob12 Caro02 Dick11 Bob02 Caro02 Caro12 Bob03 Caro11 Bob04
Honderd gevangenen — een ondervraging per dag
Stel de verroostering van ondervragingen is random. Wat is de
verwachtingswaarde van het aantal ondervragingen?
Dit is wel interessant, maar veel leuker is:
Stel er is ´e´en ondervraging per dag. Hoe lang duurt het
(gemiddeld) voor de gevangenen vrijkomen?
Honderd gevangenen — een ondervraging per dag
Stel de verroostering van ondervragingen is random. Wat is de
verwachtingswaarde van het aantal ondervragingen?
Dit is wel interessant, maar veel leuker is:
Stel er is ´e´en ondervraging per dag. Hoe lang duurt het
(gemiddeld) voor de gevangenen vrijkomen?
volger / teller / andere volger / teller / etc.
99
100
/
1
100
/
98
100
/
1
100
/ etc.
100
99
/
100
1
/
100
98
/
100
1
/ etc.
Honderd gevangenen — een ondervraging per dag
Stel de verroostering van ondervragingen is random. Wat is de
verwachtingswaarde van het aantal ondervragingen?
Dit is wel interessant, maar veel leuker is:
Stel er is ´e´en ondervraging per dag. Hoe lang duurt het
(gemiddeld) voor de gevangenen vrijkomen?
volger / teller / andere volger / teller / etc.
99
100
/
1
100
/
98
100
/
1
100
/ etc.
100
99
/
100
1
/
100
98
/
100
1
/ etc.
Bij elkaar:
99
99
X
X
100 100
1
(
+
) = 99·100+100·
= 9.900+518 dagen ≈ 28,5 jaar
i
1
i
i=1
i=1
Hoe kom je sneller vrij uit de gevangenis? Optimaliseren!
Dynamic counter assignment (protocol in two stages):
I
stage 1, 99 days: the first prisoner to enter the room twice
turns on the light. (Expectation: 13 days.)
I
stage 1, day 100: if light off, done; otherwise, turn light off.
I
stage 2, from day 101: as before, except that:
counter twice interrogated on day n counts until 100 − n only;
non-counters who only saw light off in stage 1: do nothing;
non-counters who saw light on in stage 1: do the usual. (24 y)
Head counter and assistant counters (iterated protocol, 2 stages):
I
stage 1: head and assistant counters count to agreed max. n;
I
stage 2: head counter collects from successful assistants;
I
repeat stage 1 (unsuccessful assistants continue counting to
n) and stage 2 (not yet collected successful assistants, and
newly successful assistants) until termination. (9 years)
Minimum not known!
Drie gevangenen en een beetje kennislogica
I
I
I
I
I
Gevangene 0 is de teller, gevangenen 1 en 2 zijn volgers.
p staat voor ‘het licht is aan’.
q1 staat voor ‘gevangene 1 heeft het licht aangedaan’.
q2 staat voor ‘gevangene 2 heeft het licht aangedaan’.
¬p staat voor ‘niet p’, en p → q staat voor ‘p impliceert q’.
naam actie definitie van actie
e∅
niets gebeurt
e1
p wordt q1 → p, en q1 wordt p → q1
e2
p wordt q2 → p, en q2 wordt p → q2
¬p
e0
als ¬p, dan: niets gebeurt
ep0
als p, dan: p wordt onwaar
Hoe teller 0 deze acties waarneemt:
I 0 kan e1 , e2 , en e∅ niet onderscheiden
p
I 0 kan e van de andere acties onderscheiden
0
¬p
I 0 kan e
0 van de andere acties onderscheiden
¬p,¬q1 ,¬q2
e1
p,q1 ,¬q2
0
e1
e∅
e¬p
0
¬p,¬q1 ,¬q2
e2
0
e2
ep0
ep0
0
¬p,q1 ,¬q2
e∅
e¬p
0
¬p,q1 ,¬q2
p,¬q1 ,q2
e2
0
e2
¬p,¬q1 ,q2
e1
p,q1 ,q2
ep0
¬p,q1 ,q2
0
e1
e∅
e¬p
0
¬p,¬q1 ,q2
Meer informatie
I
Honderd gevangenen en een gloeilamp, Epsilon Uitgeverij,
http://personal.us.es/hvd/lightbulb.html
I
One hundred prisoners and a lightbulb, Springer/Birkh¨auser,
Copernicus Series, verschijnt in 2015.
Proeflezers van de Engelse versie krijgen een vermelding in het
dankwoord, en bij het rapporteren van ten minste 10
(nieuwe) errata, een gratis exemplaar na verschijning. Wie wil
proeflezen, stuur s.v.p. een email naar Hans van Ditmarsch,
[email protected].
I

Download Report