Four players sit in a circle on chairs numbered clockwise from one to four. Each player has two hats, one black and one white, wearing one and holding the other. In the centre sits a fifth player who is blindfolded. That player designates the chair numbers of those whose hats should be changed. The goal is to get all four wearing a hat of the same colour, in which case the game stops. Otherwise, after each guess the four walk clockwise past an arbitrary number of chairs (maintaining the same cyclic order), then sit for the next guess.

What is the best strategy to get all four hats the same colour? Include a convincing argument why your strategy uses the fewest possible number of guesses.

Solution to MP34

We received correct solutions from Patrick J. LoPresti (USA) and Alexander Potapenko (Russia).  The solutions are essentially the same, but they differ in their approaches.

Potapenko's solution.

            If the blindfolded player were to know that the hats alternated in colour (BWBW or WBWB), then he would ask players 2 and 4 to change their hats and the game would end.  LetÕs denote this request by 0x0x.

            Were he to know only that exactly two hats are black, either they would alternate as before (BWBW or WBWB), or like colours would be adjacent (BBWW, WBBW, WWBB, or BWWB).  Request 0x0x resolves the first two arrangements while permuting the other four, then request 00xx either ends the game or changes the arrangement of colours to one of the first two, after which 0x0x ends the game.  Thus, the 3-step sequence

0x0x, 00xx, 0x0x

settles all the 2-black-hat cases.  (Note that the requirement for the cyclic order of the players to remain fixed is important only between the second and third requests.) 

            During the above 3-step procedure, those cases having an odd number of black hats get permuted among themselves.  If the game has not stopped by the third round, the blindfolded player would deduce that the game began with the players wearing 1 or 3 black hats.  The next request should therefore be 000x. This would either end the game, or switch to a state with two black hats, and the game would end using the 3-step sequence again.  He is therefore assured of a win using the 7-step sequence

0x0x, 00xx, 0x0x, 000x, 0x0x, 00xx, 0x0x.

            Let's now prove that there can be no shorter procedure that is always successful.  Without loss of generality we can assume that the players do not move and that there is some procedure that is always successful in N or fewer steps. Each step settles a particular initial arrangement of colours.  That means that no more than N initial states can be reduced to BBBB, and no more than N initial states can be reduced to WWWW.  Thus, no more than 2N initial states lead to victory.  But there are 2⁴ possible initial states, of which BBBB and WWWW end the game before the first request, so that there are 14 nontrivial initial states.  That means we need at least N = 7 steps to be assured of a win.

LoPresti's solution.

            We analyze this problem by keeping track of the set S_i of possible states after move i, with S₀ being the initial set.  We will figure out the next set of possible states for each request followed by an unknown rotation. 

            The 16 possible arrangements of four black or white hats fall naturally into four types (equivalence classes):

            1.  All hats are the same colour (2 arrangements), represented by 0000.

            2.  There is an odd number of each colour (8 arrangements):  0001.

            3.  Exactly two hats are white and they are in adjacent chairs:  0011.

            4.  Exactly two hats are white and they are in opposite chairs:  0101.

There are likewise four types of moves, of which one is trivial (where all or no hats change colour).  The trivial move changes no state, so it would never be part of an efficient strategy.  The three useful moves are

            Move Type1.  Ask for an odd number of chairs to change hats; this move changes

            Move Type 2.  Ask for two adjacent chairs to change hats; this move changes

            Move Type 3.  Ask for two opposite chairs to change hats; this move changes

            We are finally ready to solve the problem, one move at a time.  We start in state S₀ with everything being possible:

S₀ = {0001, 0011, 0101}.

We note that the first two types of moves fail to change S₀, so the first move must be Move Type 3: opposite chairs change hats.  Applied to S₀ this move either ends the game or produces

S₁ = {0001, 0011}.

Here Move Types 1 and 3 fail to change S₁, so use Type 2: two adjacent chairs change hats, which ends the game or brings us to

S₂ = {0001, 0101}.

Move Type 1 returns us to S₀ while Type 2 reverts to the previous state, so use Type 3 again to end the game or get

S₃ = {0001}.

Since Moves Types 2 and 3 do nothing to S₃ we must use Type 1 (have one hat change),

S₄ = {0011, 0101}.

Move Type1 reverts to the previous state while Type 2 does nothing, so use Type 3 to end the game or get

S₅ = {0011}.

Move Types 1 and 3 return us to previous states, so use Type 2 to end the game or get

S₆ = {0101}.

Finally, Move Type 3 ends the game.  Note that the sequence of moves is the same as for PotapenkoÕs solution.  In fact, here we saw that at every stage there was one and only one move that did not stand still or go backwards, so that this sequence of moves must be the only optimal sequence.

Comments from Francesco Barioli.

         We found the problem (in Italian) on the chat line

http://web.tiscali.it/no-redirect-tiscali/paololicheri/logica/l004x.htm

         More generally, it is possible to find a winning strategy when there are n = 2^h players seated around the blindfolded player.  (It seems plausible that, conversely, there would be no winning strategy for other values of n.)

To do this, consider a slightly more complicated version of the same problem: the blindfolded girl succeeds only if she can get all the hats to be white.  In this case the winning strategy requires15 steps:

1. xxxx (all hats switch)         9. xxxx

2. x0x0                                 10. x0x0

3. xxxx                                 11. xxxx

4. xx00                                 12. xx00

5. xxxx                                 13. xxxx

6. x0x0                                 14. x0x0

7. xxxx                                 15. xxxx

8. x000

         The idea is to reduce a 2n-problem into a n-problem, by considering pairs of opposite hats. Define a pair to be "d" if the colours of the two opposite hats are different, "p" if the colors are the same.  For instance (n=8), BWWB BWBB will be reduced to "ppdp." (Hats 3 and 7 are different.)

If, at the start, the reduced form is "pppp", by performing the following 15 moves

1. xxxx xxxx

2. x0x0 x0x0

3. xxxx xxxx

4. xx00 xx00

5. xxxx xxxx

6. x0x0 x0x0

7. xxxx xxxx

8. x000 x000

9. xxxx xxxx

10.x0x0 x0x0

11.xxxx xxxx

12.xx00 xx00

13.xxxx xxxx

14.x0x0 x0x0

15.xxxx xxxx

she will eventually succeed. Notice that none of the previous moves change the reduced form. If she does not succeed, she realizes that the reduced form is not "pppp". She actually can make this sequence to be "pppp" in 15 moves. Between each of these 15 moves she must repeat the 15 moves listed above. Globally she will need 255 moves. (It will be less if you only require the hats to be of the same color)

The case h > 3 follows by induction.

         Suppose now the problem is solvable for a certain number, n,of players surrounding the blindfolded player. It pretty easy to see that it is solvable also for any proper divisor of n. This fact reduces the problem to prime numbers. If n=3, the problem is not solvable. Indeed, starting form x00, any move does not change the status (unless you pick the lucky choice!). I guess for n = 5 or larger there should be groups of sequences that are invariant for any move (unless again you are lucky), but I cannot come up with a general rule.