Solution
I received correct solutions from Piotr Zielinski and Jim Guilford. One solution was received that was interesting, but not the optimal solution.
First, I posed the version archived online, which asked for the maximization of the probability that everyone is correct. That probability is 50%. It can't be any higher than that since Alice knows there are two choices for her hat, and so her success is limited to 50%. Further, in the optimal solution the expected number correct is 9.5 out of 10. It all works for n instead of 10.
In addition to the source I mentioned, an April preprint by Tanya Khovanova discusses this and similar puzzles. It presents a solution to the current problem where 7 people are guaranteed to be correct, and alludes to the solution, given below, where 9 are guaranteed correct.
The naive strategy would have each prisoner remove from consideration any color that has been declared and any color he or she sees. Then each prisoner has two to choose from and his or her true color is one of the two; so he or she has a 50% chance of success, and the overall chance of all prisoners guessing correctly is 1/210, or about 0.001. The expected number of correct guesses is 5.
Remarkably, there is a strategy that guarantees success with probability 1/2. The expected number of correct guesses will be 9.5.
As an aside, the rule about no color being repeated in the guesses is to avoid a number-theory based strategy, which is the standard approach to some problems like this. For example, in the classic problem of two hat colors and 10 people, Alice would call out the sum of what she sees modulo 2. This gives all the others enough information to determine their color.
Such a strategy can be used in this problem, too: Alice would call out the sum of what she sees modulo 11. In the absence of the no-repeat rule, everyone else would guess correctly.
But a new idea is needed in the presence of the rule, and that moves us from number theory to algebra.
Here is a strategy that guarantees that nine prisoners guess correctly, with a 50% chance that the tenth also guesses correctly. The key idea is the concept of an "even permutation," which is a permutation that is a product of an even number of transpositions.
Here is how Piotr Zielinski put it.
Imagine that the unused hat sits behind Alice, so that we have a permutation of 11 hats. Assume this permutation is even (50% chance). Here's how everybody guesses their hat color correctly.
Assume that those behind you have already guessed their hat colors correctly. Discard the colors that you see in front of you and those that you've already heard. You're left with two colors: that of your own hat and that of the unused hat. Pick the one that makes the whole permutation even.
If the permutation is indeed even, then the assumption is correct and everyone is correct. If the permutation is odd, this algorithm acts as if Alice's hat and the unused hat were swapped (which makes the permutation even). This is because nobody ever sees either hat, so the algorithm cannot distinguish between these two permutations. As a result, it guesses Alice's hat incorrectly, but is correct for everyone else.
I worked it out in more long-winded form as follows.
Call the prisoners 1 to 10 starting from Alice, and number the colors 0 to 10.
Alice imagines a ghost prisoner — number 0 — behind her, with the missing
color on the ghost's head.
Because of what she sees, she knows that she and the ghost have two specific colors, in some order. Without loss of generality, assume that the two colors she must choose from are 1 and 2. She calls out whichever of the two would (assuming she has it on her head, which of course it might not be) make the overall permutation of {0, 1, 2, ..., 10} determined by the 11 hats an EVEN permutation. Without loss of generality, suppose she calls out 1.
Now, Bob sees the hats on people #3, ..., #10, and he hears the call of 1 by Alice, so only two colors remain that he should consider. He cannot be wearing 1, since Alice called it. So the colors that are missing from what he sees will be 2 and a new color, call it 3. So Bob must decide which of 2 or 3 he is wearing.
Bob can reason as follows.
If Alice's guess is correct for her hat, then the truth is one of:
But Alice chose so as to make the permutation even if she is right. Bob can see that the first is even (it must be because of what Alice did), so he chooses 3 and is correct.
If Alice's guess is incorrect, then from Bob's view the truth is one of
The first is odd (because 213... is even), so Alice might indeed have called 1 if faced with this situation, and again Bob should choose 3. The second is even, so Alice would have had to call 3 if facing this.
So Bob has deduced that 3 is the color of his hat.
Now Charlie knows that Bob is correct, so his knowledge base is the same as Bob's and he can make a correct choice in the same way. The same is true for Diane, ...., Isabelle. Even Jill, who knows the hat colors of everyone except Alice, has to reason by permutation parity to make her choice, since she will have two colors to choose from.
[Back to Problem 1193]
© Copyright 2014 Stan Wagon. Reproduced with permission.