Puzzle
During our stay in Las Vegas, I talked to the people in our room about a puzzle I found on that interview riddles page. In this puzzle, there are three men; one always tells the truth, one always lies, and one answers at random. (You can imagine that the latter flips a coin to decide what answer to give, but of course you can't see the coin-flip taking place. You could also say, equivalently, that the coin-flipper always chooses the answer which is least helpful or most confusing to you.)
Now, you have to ask three yes-or-no questions and figure out which man is which. Each man knows who is who. You are not allowed to ask a question whose answer is unknown to the person you're asking.
One of the people in our group gave a proof that the puzzle can't be solved, but it turns out that his proof was incorrect. So I look around on the web and found a correct solution. You should ask person #1 "Is person #2 the truth-teller or person #3 the liar?".
If person #1 answers "yes", then you know that person #3 is not the coin-flipper.
If person #1 answers "no", then you know that person #2 is not the coin-flipper.
Ask the person who is known not to be the coin-flipper "Do you exist?" [or "Am I asking you a question?" or "Are you not the coin-flipper?"]; if he answers "no", he is the liar, and if he answers "yes", he is the truth-teller.
Now you can ask the person who is known not to be the coin-flipper about either of the other people (e.g., "Is the person to your left the coin-flipper?"), and you'll get an unambiguous answer which is either true or false (and you know which, since you know whether the person you're asking is the liar or the truth-teller).
This puzzle was hard (I didn't solve it myself), and the proof that it was unsolvable turned out to be wrong, which shows that you have to be very careful with proofs.
