The Hats Puzzles

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?

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?