10
$\begingroup$

Let n be an integer. n logicians standing in a circle are blindfolded and a hat of either red or blue is put on each person's head. Blindfolds are then removed; each person can now see the color of everybody's hat but her own, and is asked to guess her own.

No communication in any form is allowed after the hats have been placed. However, before the hats are placed, the logicians are allowed to gather and devise a strategy to make their guesses all correct or all incorrect.

My question is: does there exist such a strategy, such that their guesses are either all correct, or all incorrect?

$\endgroup$
2
  • $\begingroup$ For more generalized solutions to this problem, try googling Rot13(Unzzvat ungf). $\endgroup$
    – Brian
    Mar 4 at 18:30
  • $\begingroup$ I had an answer that assumed people answered in order, but I see ralphmerridew's answer doesn't require this. Is it worth adding that they answer simultaneously? Your note about communication could be understood to mean before the answers, as this is common in hat puzzles. $\endgroup$
    – Goldstein
    Mar 5 at 10:15

1 Answer 1

18
$\begingroup$

It is possible.

Guess the color you would have, assuming that there are an odd number of red hats. If the number of red hats is odd, everyone will be correct. If it is even, everyone will be wrong.

All winning strategies:

only two winning strategies: the one given above, or assuming an even number of red hats.

Choose a strategy S where always either everyone is right or everyone is wrong.
Claim: If S has everyone right when all hats are blue, then everyone is correct when there are an even number of red hats and everyone is wrong when there are an odd number of red hats.
Proof by induction on number of red hats. We are told it is true for 0 red hats.
Suppose it is true for $k-1$ red hats. Consider a case where exactly $k$ hats are red, with $k$ even. Choose a person R with a red hat. R sees exactly the same thing as when everyone else has the same, but R has a blue hat, so R must guess the same. In that second case, there are $k-1$ red hats (an odd number), so R guessed wrong, saying "red". In the case when R is wearing a red hat, R guessed the same, so R guessed correctly. Since S has everyone right or everyone wrong, everybody is right with $k$ red hats.
Similarly, with $k$ hats red, $k$ odd, then the case with R wearing blue but everyone else the same had $k-1$ red hats ($k-1$ even), so R correctly guessed blue. With R wearing a red hat, R must have guessed the same (blue), which is now wrong, so everyone is wrong with $k$ red hats.

Proof when everyone is wrong with 0 red hats goes similarly.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.