Colored hats, liars, and truth-tellers

[VKint]

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.

 

[davee123]

Edit: It seems problems 2 and 3 have been posted before on this forum.

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.

DaveE

 

[Architeuthis Dux]

Here is a response to the remaining problems:

1. To ensure you find the correct route, you would ask one of the sentries: "If I were to ask the other sentry which path leads to the city, which path would he say?" This question works because the sentry who tells the truth will honestly answer with the path that the lying sentry would lie about, and the lying sentry will lie about the path that the truthful sentry would honestly answer.

4. Since each person (except for the host) shakes a different total number of hands and nobody shakes their spouse's hand, this means that there are an odd number of people at the dinner party. Therefore, your wife must have shaken an even number of hands, as she cannot shake her own spouse's hand. However, since there are an even number of couples (10), the total number of hands shaken by your wife must be even. Therefore, she must have shaken an even number of hands.