7
$\begingroup$

Sue picks a number from 0 to 3.

Tom asks questions about the number, with yes/no answers. For example, "Is it odd" or "Is it 3?"

If Sue picked X, she is allowed to lie at most X times. For example, if she picked zero, she must always tell the truth. If she chose any other number, she can decide each question whether to lie, until she runs out of lies, after which she must tell the truth.

Tom wants to minimize the average number of questions. Sue wants to maximize it.

I think Sue's best strategy is random. Sometimes choose $0$, sometimes tell the truth when she doesn't have to. What is her strategy, and how many questions does Tom need on average?

Wei Hua Huang posed this in rec.puzzles newsgroup twenty years ago. I think we solved the worst-case number of questions, but not the average.

EDIT:

To compare, suppose Sue can pick 0 or 1, and may lie once if she picks 1.

Tom asks 'Is it 1?'. Suppose Sue says no. If she picked 1, then she has used up her lie. So, whether Sue picked 0 or 1, she has no lies left. Tom asks 'Is it 1?' again, and will get a correct answer.

Suppose Sue says yes to Tom's first question. She can't say yes if she picked $0$, so Tom now knows Sue picked $1$.

So Sue's best strategy is to say no, and it will take Tom two guesses.

$\endgroup$
  • 1
    $\begingroup$ When the game ends? $\endgroup$ – Sergio Parreiras May 22 '14 at 3:54
  • 1
    $\begingroup$ When Tom is certain of Sue's card. Does the edit help? $\endgroup$ – Empy2 May 22 '14 at 11:47
  • 1
    $\begingroup$ Where can we find the original puzzle (worst-case) and its solution? $\endgroup$ – user21820 May 22 '14 at 14:24
  • $\begingroup$ I can sometimes find it. In Google Groups, the subject was "Guess my number", the group was rec.puzzles, Wei-Hwa Huang (who I misspelt earlier) asked it on 12 Oct 1999 $\endgroup$ – Empy2 May 22 '14 at 16:12
  • $\begingroup$ In the case of only two numbers: 0 and 1, do you also think Sue's optimal strategy is random? I maybe wrong but picking the highest number seems to be a weakly dominant action for Sue, no? $\endgroup$ – Sergio Parreiras May 22 '14 at 19:38
0
$\begingroup$

We can verify each answer by asking:

Is it true to say, that if you were lying in the last question XOR you lie in this question, then $1$ is equal to $0$?

The answer for that question will be 'YES', if Sue told the truth in previous question and 'NO', if she lied, no matter if she's lying or telling the truth in this question.

Then we have:

  • Is it odd?
  • [verification]
  • Is it greater than 1?
  • [verification]

Which gives us 4 questions to be sure about the number.

We can also use this method of verification to turn every 'Guess the natural number of a liar' to normal 'Guess the natural number' (number of questions is just doubled)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.