I realised this week that 'guess your own hat colour' puzzles are actually about finding an orientation of a hypercube graph. (1/3)
There are several related puzzles in which N players stand in a circle, and a referee has placed either a red or a blue hat on the head of each player, in such a way that no player knows their own hat colour, but each player can see all the other N−1 hats. The players must each guess, simultaneously, at their own hat colour. They can pre-agree a strategy as complicated as they like, but may not communicate in any way once the hat colours are known.
Obviously no player can _reliably_ guess right, let alone all of them. But the puzzle conditions will only require some weaker criterion, like at least one correct guess, or a certain number of correct guesses, or no _wrong_ guesses (some of these puzzles allow a player to refuse to guess), or winning with a certain probability.
The standard starting example: just two players, each of whom can see only the other player's hat. They both simultaneously guess at their own hat colour. Ca
... Show more...I realised this week that 'guess your own hat colour' puzzles are actually about finding an orientation of a hypercube graph. (1/3)
There are several related puzzles in which N players stand in a circle, and a referee has placed either a red or a blue hat on the head of each player, in such a way that no player knows their own hat colour, but each player can see all the other N−1 hats. The players must each guess, simultaneously, at their own hat colour. They can pre-agree a strategy as complicated as they like, but may not communicate in any way once the hat colours are known.
Obviously no player can _reliably_ guess right, let alone all of them. But the puzzle conditions will only require some weaker criterion, like at least one correct guess, or a certain number of correct guesses, or no _wrong_ guesses (some of these puzzles allow a player to refuse to guess), or winning with a certain probability.
The standard starting example: just two players, each of whom can see only the other player's hat. They both simultaneously guess at their own hat colour. Can they guarantee that at least one of them guesses right?
(A spoiler for this puzzle will appear downthread.)
Jeff n1kdo
in reply to Simon Tatham • • •Xenotar
in reply to Simon Tatham • • •