|
Colored hats, liars, and truth-tellers
I have a few puzzles y'all might enjoy. They're not too hard, and many of you will probably have seen them before.
1. You're in a strange country, bereft of map, compass, or other navigational equipment, trying to make your way to a city you've never visited. You're traveling on the only road visible for miles. You come to a fork in the path. On each branch stands a single sentry. One of the two men always lies, and the other always tells the truth (don't ask me how you know this); you don't know which is which. You know that one, and only one, of the two available directions will take you to your destination. You are allowed to ask precisely one yes-no question of one of the two men (i.e., one or the other). What question do you ask to ensure you find the correct route?
2. An evil wizard captures 100 travelers and makes them play a diabolical game. After explaining the rules, he allows them to confer and agree on a strategy. He then lines up the prisoners in single file and, starting at the back, places a hat colored red, green, blue, or yellow onto each prisoner's head in such a way that each prisoner can see all the hats in front of him, but not his own or any behind him. He then proceeds, again beginning at the rear, to ask each prisoner what color hat he's wearing; if they answer correctly, they are allowed to go free, but it they fail, they're immediately executed. What is the maximum number of prisoners that the group can guarantee to save by means of strategy alone (i.e., no mutinies or other such trickery)?
3. Same as the last puzzle, except with an infinite number of prisoners.
4. My wife and I have ten couples over for dinner one night. During the course of the evening, I observe that each person present (except me) shakes a different total number of hands. Furthermore, nobody shakes their spouse's hand. How many hands did my wife shake?
Edit: It seems problems 2 and 3 have been posted before on this forum.
|
