Section 1.2: Problem 7 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
You are in a land inhabited by people who either always tell the truth or always tell falsehoods. You come to a fork in the road and you need to know which fork leads to the capital. There is a local resident there, but he has time only to reply to one yes-or-no question. What one question should you ask so as to learn which fork to take? Suggestion: Make a table.
Here we may try to either double the liar’s lie to negate the falsehood in his reply, or compose a question with two parts such that the liar will again be forced to say the truth.
The double negation might work as follows: “If I asked you yesterday (or, if I ask you tomorrow, or, if I were to ask you) whether the right road leads to the capital, would you say yes?” The truth teller will report whatever is the truth regarding whether the right road leads to the capital. The liar, on the other hand, would lie yesterday (or will tomorrow, or lie about it at any time), therefore, he will lie again about his own false answer, reporting the truth.
A composition of two statements can be as follows: “Is it true that you always say the truth and the right road leads to the capital or you always says a falsehood and the left road leads to the capital?” Here we compose two different statements: =”you always say the truth” and =”the right road leads to the capital”. Here is the truth table (NOT what they would report, except for the last column) for both statements and their composition in each case:
|The right road leads to the capital|
|The left road leads to the capital|
So, the idea is to simply form a statement that in the case the right roads leads to the capital is true for a truth-teller and false for a liar (so, both would report “Yes”), and vice versa in the case the left road leads to the capital (so, both would report “No”).