Guessing Hats 2

9 wise men are guaranteed to survive. The 1st wise man has a 50/50 chance.

Let’s call the wise men P1 (back of line) through P10 (front of line). P1 can see all 9 hats in front of him. He has zero information about his own hat, so at best he can guess randomly and survive with probability 1/2.

However, P1’s answer can encode information that helps everyone else. The strategy works by using his answer to communicate the parity of black hats he sees.

Here’s the protocol: P1 counts the number of black hats he can see. If the count is odd, he says “black”. If the count is even, he says “white”. This gives him a 50/50 chance of being correct about his own hat.

P2 now has enough information to deduce his own hat colour. He heard P1’s answer, which tells him the parity of black hats among P2 through P10. P2 can see the 8 hats in front of him. He counts the black hats he sees and compares this count to the parity P1 announced.

If P2 sees an odd number of black hats and P1 said “black” (meaning the total count of P2-P10 was odd), then P2 must be wearing a white hat. If P2 sees an even number of black hats and P1 said “black”, then P2 must be wearing a black hat. P2 announces his hat colour correctly and survives.

P3 now knows two things: the original parity from P1, and P2’s hat colour (which P2 announced). P3 can see 7 hats in front of him. He counts the black hats he sees, adds P2’s hat (if black) to his count, and compares this running total to the original parity. From this, he deduces his own hat colour.

This process continues down the line. Each wise man uses the original parity information from P1, the announced colours of everyone behind them, and the hats they can see in front of them to deduce their own hat colour.

Can we do better? No. P1 cannot have any information about his own hat. He can see 9 hats, and both “all black” and “all white” are consistent with him wearing either colour. The best he can do is use his answer to help others. Thus, 9 guaranteed survivors is optimal.