Simon Says

The Strategy

The guests assign each guest and each colour a number from to . Guest assumes that the sum of all the hat-numbers is . Exactly one of the guests will be correct.

The Strategy

The guests assume that the number of, say, red hats is even. If this is true (p=1/2), they will all guess correctly. If not, they will all be wrong.

Analysis

To show that we cannot do better than this, consider a particular guest called Alice. Alice knows nothing about the colour of her own hat, so there is no strategy that gives her a chance of guesssing correctly greater than 1/2. If Alice does not guess correctly, the guests cannot win.

The Strategy

The guests stand in a circle. If you see two hats the same, you guess that your hat is the other colour. If you see two hats of different colours, you guess that your hat is the same colour as that of the guest on your left.

Analysis

If all three hats are the same colour (p=1/4), everyone will be wrong and the guests lose. However, if there are two of one colour and one of the other colour (p=3/4), then the odd-hat-out guest and one of the other guests will be correct, so the guests win.

To show that we cannot do better than this, again consider Alice. There are 8 possible hat assignments, so let's imagine 8 different universes, each with its own party. In every universe where Alice has a red hat, there is a corresponding universe where everything is the same except that Alice has a blue hat.

As everything else is the same, the input to Alice's strategy is the same, so she must make the same guess in both universes. Over all the universes, Alice will be correct in half of them. Over all players in all universes, there are guesses, and 12 of these guesses are correct. A universe needs 2 correct guesses to win the game, so we cannot do better than 6 of the universes winning.

The Strategy

If a guest sees two hats the same colour, they guess that their hat is the other colour. If they see two hats of different colours, they pass.

Analysis

If all three hats are the same colour (p=1/4), everyone writes down an incorrect guess and the guests lose. If one hat is different to the other two (p=3/4), the guest wearing that hat guesses correctly and the other two pass, so the guests win.

To show that we cannot do better than this, again imagine 8 parallel universes. For every time that Alice guesses correctly, there is another universe where she guesses incorrectly. But this time, there are also universes where she passes. The same is true of all other guests, so if we tally up across all guests and all universes, there must be the same number of correct and incorrect guesses.

A winning universe is one with at least one correct guess and no incorrect guesses. The strategy given here leads to 6 winning universes out of 8. Any strategy that could beat this would need to win in 7 or more universes, so the strategy would need to have 7 or more correct guesses spread across all universes. But then it would also need at least 7 incorrect guesses, which wouldn't all fit into the one losing universe. So such a strategy doesn't exist. However, there are other strategies with the same win rate as the one presented here.

The Strategy

Before they get their hats, the guests agree on the following scheme. They will map red hats to the number 0 and blue hats to the number 1. Let be the colour of Alice's hat, be the colour of Bob's hat, and so on. They will compute the following checksums:

The symbol stands for addition modulo 2, so are each either 0 or 1.

Of course, the guests don't know the colour of their own hats, so Alice can't compute and George can't compute any of these! So what do they do? They assume that not all three of these are 0. If this assumption is sufficient to uniquely constraint the colour of their own hat, they guess that colour. Otherwise, they pass.

Alice will look around, and calculate and . If either of these is 1, she passes. But if they are both 0, she can work out what value of would make be equal to 1.

Charlie will look around and calculate . If this is 1, he passes. If it is 0, he calculates and . If these values are both 0, he knows the only way for not all three of are 0 is if . Similarly, if both of his values are 1, it must be that . And if he calculates two different values, he knows the condition is satisfied, but doesn't know what to guess, so he passes.

George will calculate , , and . He only makes a guess if all these values are the same.

Let's look at what happens in an example. Suppose everybody was given a red hat, so . Then . Everyone will incorrectly assume that the checksums they haven't calculated are 1, and therefore make an incorret guess as to the colour of their own hat. In this case, the guests lose.

In another example, suppose everyone has a red hat except Alice, who has a blue hat. Now, . What does each person do?

• Alice calculates that , so she assumes . She correctly guesses that her own hat is blue.
• Bob calculates that . He passes because he already knows that the checksums are not all 0.
• Charlie calculates that . He passes.
• David calculates that . He passes.
• Eve calculates that . She passes.
• Fred calculates that . He passes.
• George calculates that . He passes.

Alice has guessed correctly, and everyone else has passed. So the guests win.

Whenever the assumption that not all of are 0 holds, there will be exactly one guest who is able to work out the colour of their hat, and the other 6 will pass. Whenever the assumption does not hold, all the guests will write down an incorrect guess. How often does the condition hold? These are independent Bernoulli random variables , so they are all 0 with probability 1/8 and therefore the guests lose with probability 1/8 and win with probability 7/8.

Analysis

You may well wonder how anyone could came up with the checksums above. They are actually based on the Hamming code , an error-correcting code designed to provide robustness against random bit-flips during data storage or transmission. The data source would want to send 4 bits, . They compute such that , and then transmit . During transmission, if one of these bits gets corrupted, the reciever will notice and, moreover, be able to figure out which one was wrong. If two or more bits get corrupted, the message is lost. (There are other error-correcting codes that can deal with 2 or more errors).

To figure out which variables to include in which equations, take the variable and write in binary. Then include that variable in the equations where the binary representation of has a 1. So, the 5 ^th variable, which is , is included in the first and third equations, because the binary representation of 5 is 101, with a 1 in the 1st and 3rd columns. In this way, it is guaranteed that each data bit is included in a unique set of equations, so we can use the set of equations that fail the checksum check to work out which bit was corrupted during transmission.

We can view the solution to 4.1 in a similar way, too, with checksums and .

In fact, a Hamming code exists that can be used for a party of guests, where they will win with probability

To show that our party guests cannot do better than this strategy, we can generalise from the previous game. This time, we will need to imagine 128 parallel universes. For every correct guess in one universe, there is an incorrect guess in a different one. The best we can hope for is for all losing universes to be filled with 7 incorrect guesses, and for all winning universes to have just the 1 correct guess they need. This leads to a 7:1 win-loss ratio.

The Strategy

The guests sort all possible hat assignments into equivalence classes under the relation iff and differ in finitely many places.

They then invoke the Axiom of Choice to map each equivalence class to a representative element of that class.

At the party, each guest can look around at everybody else's hats and work out which equivalence class they are in. They don't know the colour of their own hat, but that's not a problem because that introduces only 1 more difference, and a finite number plus 1 is still a finite number.

Then, they guess the colour of hat they would have under the representative of this class.

Only finitely many guests will guess incorrectly, so they win.