74. 100 prigionieri e la lampadina

100 prigionieri sono in celle isolate. C'è una stanza comune con una lampadina (inizialmente spenta). Ogni giorno, una guardia sceglie un prigioniero a caso e lo porta nella stanza. Il prigioniero può accendere, spegnere o lasciare invariata la lampadina. Non può comunicare in altro modo.

Prima dell'inizio, i prigionieri possono concordare una strategia. In qualsiasi momento, un prigioniero può dichiarare "Tutti i 100 prigionieri sono stati nella stanza almeno una volta". Se ha ragione, tutti sono liberi; se sbaglia, tutti muoiono.

Qual è la strategia e quanto tempo ci vorrà in media?

Suggerimento

Designa un prigioniero come "contatore". Solo lui può spegnere la lampadina. Gli altri possono accenderla solo una volta.

Risposta

La strategia richiede circa 28 anni in media.

Strategia:

  1. Designa un prigioniero come "capitano" (contatore)
  2. Ogni altro prigioniero: la prima volta che trova la luce spenta, la accende. Poi non tocca più l'interruttore.
  3. Il capitano: ogni volta che trova la luce accesa, la spegne e incrementa il suo contatore mentale.
  4. Quando il contatore del capitano raggiunge 99, dichiara che tutti sono stati nella stanza.

Tempo medio: Con 100 prigionieri e selezione casuale giornaliera, il tempo atteso è circa 10.000+ giorni (circa 27-28 anni) per completare il conteggio.