The Hats Puzzle

Puzzle 1: There's an old puzzle in which the king blindfolds three ministers, places a white or black hat on each one and removes the blindfolds. "If you can see a black hat, raise your hand", he says. They each raise a hand. "If you can tell what color your hat is, raise your hand." All the hands drop. Then suddenly, one minister raises his hand. What color was his hat?

Puzzle 2: Another king has four ministers. He shows them a table with two white hats and two black ones. He blindfolds them, and places a hat on each. Then, he puts one on one side of a wall, and the other three in a line on the other side, facing the wall, like so:

        A  |  B  C  D
A and B can see nothing but the wall. C can see B's hat. D can see B's hat and C's hat. Assuming the ministers are good thinkers, will someone be able to determine their hat color?

Puzzle 3: On a certain island with 500 married couples. In exactly 50 of those couples, the husband is committing adultery. The way gossip works on this island, everyone is very polite, so no one will tell a wife that her husband is committing adultery, but they will certainly tell her about all the other husbands. So let us suppose that every wife of a cheating husband knows about the other cheating husbands, but not her own.

One day, the executioner appears in the town square and says, "Any wife who suspects her husband of cheating shall bring him to me today!" But no one brings a husband forth. The next day, the executioner shows up again, but no husband is brought forth. The executioner is stubborn, and so he comes every day. Is justice ever done?

Puzzle 4: We return to the first problem, but now the rules have changed. The king tells his three ministers, "In five minutes, I am going to come back into this room, blindfold you, place a white or black hat randomly on each of you, then unblindfold you. When I count to three, say the color of your hat, or stay silent. If you all stay silent, I will hang you all. If anyone guesses the color of their hat incorrectly, I will hang you all. But if no one guesses incorrectly, and at least one of you guesses correctly, you all live." Assuming the ministers would like to live, what is a sensible strategy for the ministers to agree on before the king returns?

Puzzle 5: The king has N ministers, whom he places in a line of chairs facing forward, so that person N can see all the other ministers, and person 1 sees nobody. There are N-1 black hats, and 1 white hat. These are placed on the minister's heads in the dark. When the lights come on, the king begins with minister N, and proceeds down to minister 1, and asks each "Do you know the color of your hat?". Suppose one of the ministers can't make it to the test, and you have to go instead. If you get your choice of seats, where should you sit?

Puzzle 6: Archimedes, Boole, and Chebyshev, three perfectly wise thinkers, each has a hat on his head, on which is written some positive integer. The host then announces that the number on one of the hats is the sum of the numbers on the other two hats. The following statements are made:

  1. Aristotle: I cannot determine my number.
  2. Boole: I still cannot determine my number.
  3. Chebyshev: I also still cannot determine my number.
  4. Aristotle: My number is 50.
Aristotle is correct. From this fact, and from the four remarks, can you determine how Aristotle determined his number, and what the numbers on the other two hats were?

Puzzle 7: we revisit puzzle #4, but with a few 'minor' modifications! We now suppose there are a countably infinite number of ministers. The king will place a black or white hat on each minister, each will be able to see all hats but his own, and they will all be required to guess, simultaneously, the color of their hat. (A silent response is not allowed in this version!) The king, being a kind king, will not execute the ministers, as long as only finitely many of them are wrong in their guesses. It seems hopeless, but they have five minutes to agree on a strategy before the king comes back with the hats. Is there some way to maximize their chances of survival?

I give up, show me the solution.

Last revised on 17 July 2007.