The magician gives each of $2^n - 1$ prisoners a hat, which is colored black or white. Each prisoner's hat color is likely to be white as much as it is likely to be black (each prisoner's hat color is chosen in random with probability $0.5$ for each color).
Each prisoner can see everyone else's hats, but not his own hat. Then, they all have to shout at the same time their guess for their hat color: "Black/White/I don't know". They win if and only if at least one prisoner guessed right, and no prisoner guessed wrong (the magician wins if someone guessed wrong or if they all said "I don't know").
Find a strategy such that the prisoners will win with the highest probability.
I have found a strategy in which the prisoners win with probability $
1-\frac{1}{2^n}$, but I don't know how to prove this is optimal.
The strategy is: let the prisoners number themselves from $1$ to $2^n-1$, so each prisoner is a unique $n$-digit number in base $2$. Each prisoner calculates the $
\oplus$ operator (xor operator) of all the prisoners' numbers he sees who have black hats. If he gets the result $0$, he guesses "black". Otherwise he guesses "I don't know". This strategy will work if and only if the $\oplus$ operator on all the people with black hats is $\neq 0$, so it's probability $1-\frac{1}{2^n}$. I'm pretty sure it is optimal, but how to prove it?
2026-04-02 00:44:14.1775090654