Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Colored hats, liars, and truth-tellers

  1. Apr 29, 2009 #1
    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.
  2. jcsd
  3. Apr 29, 2009 #2
    I think they've all been posted before, although with slightly different variants. The handshake one I remember seeing here and solving, but with a smaller number of couples. The 1st problem is posted here a LOT in different forms, and the 2nd one is again mildly common.

    The 3rd one is particularly interesting to me, because someone posted something similar which I still disagree with. He was claiming that with an infinite (yet "countable") number of prisoners, AND with each person not being able to hear the guesses of the people behind them, that you could save EVERYONE except some finite number.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook