Skip to main content
MathOverflow

Return to Answer

added 100 characters in body; deleted 2 characters in body
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

Specifically, to be a bit more definite about what it means to give a wrong answer, I propose that the rules should allow that the second player, at most once during the game, decides that a given round will be a lie-telling round, for which he will privately ponder the correct truthful answer, but then give as his answer precisely the opposite of the correct answer. So if a truthful answer would have been Yes, then on this lie-telling round he says No, and conversely. (In particular, in this version of the game, the wrong answer is not a random answer in any sense, although it could be that the choice of which round is to be a lie-telling round is determined randomly.) On the other rounds, he tells the truth. Secondly, I note that you didn't insist that the questions of player 1 must have a particular form.

  • "IfIf I were to have asked $Q$ on this round, would you have said Yes?"

Specifically, to be a bit more definite about what it means to give a wrong answer, I propose that the rules should allow that the second player, at most once during the game, decides that a given round will be a lie-telling round, for which he will privately ponder the correct truthful answer, but then give as his answer precisely the opposite of the correct answer. So if a truthful answer would have been Yes, then on this lie-telling round he says No, and conversely. (In particular, in this version of the game, the wrong answer is not a random answer in any sense, although it could be that the choice of which round is to be a lie-telling round is determined randomly.) On the other rounds, he tells the truth.

  • "If I were to have asked $Q$ on this round, would you have said Yes?"

Specifically, to be a bit more definite about what it means to give a wrong answer, I propose that the rules should allow that the second player, at most once during the game, decides that a given round will be a lie-telling round, for which he will privately ponder the correct truthful answer, but then give as his answer precisely the opposite of the correct answer. So if a truthful answer would have been Yes, then on this lie-telling round he says No, and conversely. (In particular, in this version of the game, the wrong answer is not a random answer in any sense, although it could be that the choice of which round is to be a lie-telling round is determined randomly.) On the other rounds, he tells the truth. Secondly, I note that you didn't insist that the questions of player 1 must have a particular form.

  • If I were to have asked $Q$ on this round, would you have said Yes?
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

The other answers are truly excellent and have settled the intended question. For a bit of fun, however, allow me to mention the following paradoxical solution.

Namely, with a certain precise and reasonable understanding of the rules of your game, which I shall presently give, I claim that no additional questions are required for the lie-telling game over the truth-telling game. In particular, in your case 10 questions still suffice!

Specifically, to be a bit more definite about what it means to give a wrong answer, I propose that the rules should allow that the second player, at most once during the game, decides that a given round will be a lie-telling round, for which he will privately ponder the correct truthful answer, but then give as his answer precisely the opposite of the correct answer. So if a truthful answer would have been Yes, then on this lie-telling round he says No, and conversely. (In particular, in this version of the game, the wrong answer is not a random answer in any sense, although it could be that the choice of which round is to be a lie-telling round is determined randomly.) On the other rounds, he tells the truth.

With these rules for the liar game, I claim that no additional questions over the fully truthful case are required to determine the secret number.

The reason is a simple logic trick: if in the fully truthful game, one would want on a round to ask a question $Q$, then in this liar game, one should instead ask the question $P$:

  • "If I were to have asked $Q$ on this round, would you have said Yes?"

Consider how the second player will react. First, if he is on a truth-telling round, then he will give the same answer to this question that he would have given to $Q$. If in contrast he is on a lie-telling round, then he ponders question $P$, and considers that if the first player had asked $Q$ on this round and a truthful answer had been Yes, then he would have said No, since this is a lie-telling round, and so a truthful answer to $P$ is No, but since it is a lie-telling round, he answers Yes to $P$. Similarly, if a truthful answer to $Q$ would have been No, then a lie-telling answer to $Q$ would be Yes, and so a truthful answer to $P$ would be Yes, but since it is a lie-telling round, he answers No. Thus, because of the double-negation effect, the lie-telling answer to $P$ is the same as the truth-telling answer to $Q$.

Therefore, the first player can in effect gain exactly the same information from the second player in the liar game that he can in the fully truth-telling game.

The same argument shows that, in fact, it doesn't matter how often the second player decides to lie, as long as he lies by stating each time the exact opposite of a truthful answer. Indeed, the second player could randomly decide for each round whether he will lie or tell the truth on that round, but the double-negation trick of question $P$ allows the first player nevertheless to gain exactly the same information, and so no additional questions beyond the truth-telling case are required, even if the second player decides randomly at the beginning of every round whether to lie or tell the truth on that round.

Ha!