Everyone guesses their hat at once

Question

N prisoners each wear a hat labeled with a number from 0 to N-1 (numbers may repeat, assigned adversarially). Each prisoner sees everyone else's hat but not their own. Simultaneously, with no communication, every prisoner writes down a guess for their own number. Devise a strategy that guarantees at least one prisoner guesses correctly, no matter how the hats are assigned.

Accepted Answer

The strategy. Number the prisoners 0, 1, \dots, N-1. Let S = \sum{i} hi be the (unknown) total of all hat numbers. Prisoner k assumes the total is congruent to k modulo N, and guesses accordingly: gk = \left(k - \sum{i 
eq k} hiight) \bmod N. Prisoner k can compute this because they see everyone else's hats (the sum \sum{i 
e k} hi). Why at least one is right. Prisoner k's guess is correct exactly when their own hat hk makes the total satisfy their assumption: gk = hk \iff hk \equiv k - \sum{i
eq k} hi \pmod N \iff \sumi hi \equiv k \pmod N \iff S \equiv k \pmod N. Now, the actual total …

Everyone guesses their hat at once

Your answer

More Brainteasers questions