## 1997-03 Solution

by Not-Sure-I-Heard-It-Long-Ago

There are two solutions: The standard one and mine. Both have the property that the answer is independent of the truthtellingness of the person you ask. The standard one is:

If I were to ask the other native if the right path is correct, what would he say? (if answer is "NO", take the right one. If answer is "YES", take the left one)

Let's make a table:
Native \ Path Right path is correct Right path is wrong
Truthteller NO
(Liar would lie, say NO, which truthteller correctly reports)
YES
(Liar would lie, say YES, which truthteller correctly reports)
Liar NO
(Truthteller would say YES, liar reverses it to NO)
YES
(Truthteller would say NO, liar reverses it to YES)

The second solution, mine, is the following question:

If I were to ask you if the right path is correct, would you say "YES"? (if answer is "YES", take the right one. If answer is "NO", take left one)

Let's make a table:
Native \ Path Right path is correct Right path is wrong
Truthteller YES
(Truthteller would initially say YES then truthfully report that he had just said YES)
NO
(Truthteller would initially say NO then truthfully report that he had not said YES)
Liar YES
(Truthteller would initially say NO then lie when he reported that he had not said YES)
NO
(Truthteller would initially say YES then lie when he reported that he had just said YES)

WWW Maven: Dan Garcia (ddgarcia@cs.berkeley.edu) Send me feedback