|
This month's IEEE GlobalSpec Specs & Techs newsletter challenge is:
A traveling logician in a faraway land comes to a fork in the road, wanting to know which of two roads leads to the nearest village. She is approached by three willing natives, one each from a tribe of invariable truth-tellers, a tribe of invariable liars, and a tribe of random answerers. Of course the logician doesn’t know which native is from which tribe. Moreover, she is permitted to ask only two yes-or-no questions, each question being directed to just one native. Can she get the information she needs to get to the village?
And the answer is:
The solution, inspired by mathematical physicists Vladas Sidoravicius and Senya Shlosman, is below.
It seems impossible to deal with the random answerer, but it's not. You need to be sure the second native you query is not the random asnwerer. This is necessary because you’re not going to know the road after the first question, and if the second responder is random you won’t learn any more.
On the other hand, this objective is sufficient, because you can then use the traditional two-native query as your second question: namely, something like “If I were to ask you whether this road goes to the village, would you say yes?”.
To attain the objective, you’ll need to ask Native A something about Native B or Native C, then use the answer to choose between B and C. Here’s one that works: “Is B more likely than C to tell the truth?”
Curiously, if A says “yes” you pick C, and if he says “no” you pick B! If A is the truth-teller you want next to query the companion who is less likely to tell the truth, namely, the liar. If A is the liar you want the more truthful of his companions, namely the truth-teller.
Of course, if A is the random answerer it doesn’t matter which of B and C you turn to next.
Note: This puzzle is an expansion of Martin Gardner's famous two-native problem, in which the logician is confronted by two natives (no random answerer) and can ask only one question of one of them. The answer to that puzzle is to ask either native "If I were to ask you if this road leads to the village, would you say yes?" Phrasing the question in that way forces the liar to answer "yes" if it is the correct road -- since the truth-teller will also answer "yes" to the correct route.
|
Good Answers:
"Almost" Good Answers: