Cento prigionieri e una lampadina

Non è necessario che tutti conoscano il numero di visitatori. Basta che una sola persona possa raccogliere le informazioni.

Assegna a un prigioniero un ruolo diverso. Gli altri devono poter inviare un segnale che resti disponibile finché non viene letto.

Un segnale ancora acceso non può essere sovrascritto da un secondo segnale distinguibile.

Chi vuole segnalare deve aspettare di trovare la lampadina spenta. Dopo aver segnalato una volta, deve ricordarsene per sempre e non ripetere il messaggio.

Prima dell’isolamento designano un contatore. Gli altri 99 sono segnalatori. Il contatore parte da zero; ogni segnalatore ricorda se ha già inviato il proprio segnale.

• Un segnalatore che non ha ancora segnalato accende la lampadina soltanto se la trova spenta. Da quel momento considera il suo segnale inviato.
• Se la lampadina è già accesa, il segnalatore la lascia accesa: non ha ancora inviato nulla e riproverà in una visita futura.
• Dopo aver inviato il proprio segnale, un segnalatore non tocca più l’interruttore.
• Il contatore, quando trova la lampadina accesa, la spegne e aumenta di uno il proprio conteggio. Se la trova spenta, non cambia nulla.
• Quando il contatore raggiunge 99, dichiara che tutti hanno visitato la stanza.

Perché non può sbagliare? Ogni accensione proviene da uno dei 99 segnalatori, e ciascuno accende al massimo una volta. Solo il contatore spegne, quindi una stessa accensione non può essere contata due volte. La lampadina inizialmente spenta esclude segnali precedenti alla prima visita. Novantanove segnali contati corrispondono dunque a 99 persone distinte; il contatore è la centesima ed è presente nella stanza.

Perché prima o poi termina? Quando la lampadina è spenta e restano persone che non hanno segnalato, ogni turno ha probabilità positiva di selezionarne una. La probabilità di evitarle per sempre è zero. Dopo l’accensione, il contatore viene selezionato prima o poi con probabilità 1 e libera il canale spegnendo.

Ripetendo questo ragionamento per un numero finito di segnali, tutti vengono raccolti con probabilità 1. La strategia non dichiara mai il falso, qualunque sia la sequenza delle visite. Esistono però sequenze infinite che impediscono la conclusione: nel modello casuale hanno probabilità zero.

99 segnali distinti + il contatore presente = 100 visitatori certi.

La lampadina è una memoria condivisa di un bit. Le memorie personali contengono il resto: ogni segnalatore ricorda un sì o un no, mentre il contatore conserva un numero. Il protocollo funziona perché assegna significati univoci alle azioni e separa invio e ricezione.

Possiamo descrivere un invariante: il numero dei segnali già inviati è uguale al conteggio del contatore più 1 se la lampadina è accesa, oppure al solo conteggio se è spenta. Questa relazione rimane vera dopo ogni visita. È il motivo per cui i messaggi non vengono né inventati né persi.

La sicurezza della dichiarazione non dipende dalla casualità. Per la conclusione basta anche una sequenza deterministica equa, nella quale ciascuno venga chiamato infinite volte. Senza alcuna condizione di questo tipo, il carceriere potrebbe escludere per sempre una persona.

Nel modello indipendente e uniforme possiamo calcolare il tempo medio di questa strategia. Se restano k segnalatori da contare e la lampadina è spenta, l’attesa media per una nuova accensione è 100/k turni. Dopo l’accensione occorrono in media 100 turni per chiamare il contatore. Sommando per k da 99 a 1:

E[T] = 100 · (1 + 1/2 + … + 1/99) + 9900 ≈ 10417,74 turni

È la media di questo protocollo, non una prova che sia il più rapido possibile. Non esiste un limite deterministico al tempo d’attesa: per ogni durata finita rimane una probabilità positiva di non aver finito. Se ogni turno fosse un giorno, la media supererebbe 28 anni.

E se lo stato iniziale fosse sconosciuto? Le altre ipotesi restano identiche. La regola precedente potrebbe scambiare un’accensione iniziale per una visita: come correggerla?

Una soluzione è far inviare a ciascuno dei 99 segnalatori due segnali, sempre accendendo solo quando trova spento e senza spegnere mai. Ognuno tiene memoria di zero, uno o due invii. Il contatore spegne e conta come prima, ma aspetta di arrivare a 198.

Se anche un solo segnalatore non fosse mai entrato, gli altri 98 potrebbero generare al massimo 196 segnali. Aggiungendo l’eventuale accensione iniziale si arriverebbe al massimo a 197. Quindi 198 garantisce che tutti abbiano visitato. Non garantisce che tutti abbiano già inviato entrambi i segnali, ma questo non è l’obiettivo.

La conclusione arriva ancora con probabilità 1: se inizialmente era spento, sono disponibili 198 invii reali; se era acceso, c’è in più un possibile segnale iniziale. Lo stesso alternarsi fra accensione e lettura impedisce che il processo resti bloccato.

Questo rompicapo illustra due proprietà studiate anche nei sistemi distribuiti: la sicurezza, cioè evitare un risultato scorretto, e il progresso, cioè arrivare infine a un risultato. Una procedura può avere la prima senza la seconda. Qui il protocollo assicura la sicurezza, mentre la regola delle visite rende possibile dimostrarne il progresso.

Una versione del rompicapo e della soluzione compare nella raccolta di John Burkardt presso Florida State University. Le varianti cambiano le informazioni iniziali: prima di trasferire una soluzione, conviene controllare queste ipotesi.

Il gioco è diverso da I cento prigionieri e le cento scatole: là si sfruttano i cicli di una permutazione, qui si costruisce un canale di comunicazione persistente.