A Fork in the Road
Solutions to the puzzles
Puzzle 1
Suppose there are two trolls at this fork in the road. One always tells the truth and the other always lies but you don’t know which is which. You have only one gold coin to pay one of them to answer a question. What question will you ask one of them to be 100% sure of which fork to take?
Answer
You simply select one of the trolls randomly and ask, “If I asked the other troll which way I should take, what would he say?” If you selected the lying troll, he would know that the other troll would have told the truth, so the lying troll will lie about the answer. The correct answer, then, is the opposite of what the lying troll would say. On the other hand, if you selected the truthful troll, he would truthfully tell you what the lying troll would say, a lie, and you should therefore take the opposite of his answer. In either case, you should always choose the road that is the opposite of the answer you receive, guaranteeing with certainty that you select the correct road.
Puzzle 2
You are lost in a country in which one third of the inhabitants always lie. The other inhabitants tell the truth, but only three quarters of the time. Desperate to get out of the country, you come to a fork in the road guarded by a troll. One way leads out and the other to certain death, but you don’t know which is which. You can ask the troll which way is out if you pay him a gold coin. You have four gold coins.
You pay the troll a gold coin and he advises you to go right. Does that answer help you to decide?
You pay the troll another gold coin and he advises you to go right again. Does that answer help you to decide?
You pay the troll another gold coin and he advises you to go right yet again. Does that answer help you to decide?
You pay the troll your last gold coin and he advises you to go left this time. You must make a final decision. What should you do?
What is the chance you get out of this country alive after you’ve paid your last gold coin?
Answer
The variation is good bit harder, requiring some probability calculations. Let’s define some events first. Sn is the event that the troll gives the same answer n times. T is the event that the answer is true. D is the event that the troll is dishonest but not a total liar, i.e., he lies one fourth of the time. The probability we want is P(T|Sn), the conditional probability the response is true given that we have been given the same response n times. By the properties of conditional probability,
P(Sn )= [(3/4)n +(1/4)n]*(2/3)+1/3, since 2/3 of the time n truthful answers will be given with probability 3/4 or n false answers will be given with probability 1/4, or 1/3 of the time n false answers will be given with probability 1.
The troll’s first answer is “go right.” What is the probability that answer is truthful? P(S1 )= [(3/4)1 +(1/4)1]*(2/3)+1/3 =1. Therefore, P(T|S1) = (3/4) * (2/3)/1 =1/2. Unfortunately, the first answer doesn’t improve the odds from 50-50.
The troll’s second answer is “go right.” The probability it is truthful is P(T|S2) = (3/4)2 * (2/3)/ P(S2 ). But P(S2 )= [(3/4)2 +(1/4)2]*(2/3)+1/3 = (10/16)*(2/3)+1/3 = 18/24 = 3/4. Therefore, P(T|S2) = (3/4)2 * (2/3)/(3/4) = (3/4)*(2/3) = 1/2. The second answer doesn’t help either—it’s still 50-50 odds.
The troll’s third answer is “go right.” The probability it is truthful is P(T|S3) = (3/4)3 * (2/3)/ P(S3 ). However, P(S3 )= [(3/4)3 +(1/4)3]*(2/3)+1/3 = (7/16)*(2/3)+1/3 = 5/8. So, P(T|S3) = (3/4)3 * (2/3)/(5/8) = 9/20. The probability that the third answer is true is slightly under a half. That helps a little, but not much.
However, the fact that the troll changed his answer on the fourth question helps tremendously, since it shows that he’s dishonest but not a total liar. We now know that he either gave three truthful answers and one false one, or he gave three false answers and one truthful one. Let R be the event that going right is a truthful answer and A be the event that he gave three truthful answers and one false one or three false answers and one truthful one. We want to calculate P(R|A).
When the troll changed his answer, we became 90% certain that going right is the correct road to take, even though he advised us to go left the fourth time we asked.
What would happen if the troll never changed his answer? You could never be certain the troll is a liar based on that, but you would become more and more convinced he’s a liar if he kept giving you the same answer. How many gold coins would you need to become at least 95% sure that his answer is a lie? You would need to find n such that P(T|Sn) <= 5%. If n = 13, P(T|S13) = 4.5%, so you’d need 13 gold coins.