39. 100 prigionieri e cappelli colorati

100 prigionieri sono in fila, uno dietro l'altro. A ciascuno viene messo un cappello rosso o nero. Ogni prigioniero può vedere i cappelli di tutti quelli davanti a lui, ma non il proprio né quelli dietro.

Partendo dall'ultimo della fila (quello che vede tutti gli altri), ogni prigioniero deve dire ad alta voce "rosso" o "nero". Se indovina il colore del proprio cappello, è salvo.

I prigionieri possono accordarsi su una strategia prima. Qual è la strategia che massimizza il numero di prigionieri che si salvano con certezza?

Suggerimento

Il primo prigioniero (in fondo alla fila) può comunicare un'informazione utile a tutti gli altri. Pensa alla parità: quanti cappelli rossi vede?

Risposta

99 prigionieri si salvano con certezza, il primo ha il 50% di probabilità.

Strategia della parità: il primo prigioniero conta i cappelli rossi che vede. Se sono in numero pari, dice "rosso"; se sono dispari, dice "nero". (Potrebbe indovinare o no il proprio cappello - 50% di probabilità).

Il secondo prigioniero conta i cappelli rossi davanti a lui. Confrontando con l'informazione sulla parità, deduce il proprio colore. Poi dice il colore corretto.

Ogni prigioniero successivo tiene traccia della parità originale e di quanti cappelli rossi sono stati detti, e può dedurre il proprio colore.