# Guess a number part 5. Alice Lies!

Probability Level 3
• Alice: "Hey Bob, I'm in the mood for some sneakiness. Want to play a variant of 'Guess a Number'?"
• Bob: "Sure."
• Alice: "Let's play the two-round version where you submit a list of yes/no questions, then I answer them, and then you guess one number. This time I will answer all of your questions."
• Bob: "Good!"
• Alice: "But on one of the questions (of my choosing) I may lie. Or maybe I won't."
• Bob: "Okay, I think I can do this."

So, Alice thinks of a number between 1 and 1000, and Bob makes up a list of 15 questions.

Alice then receives the list, answers all of the questions with yes or no, with the guarantee that at least 14 are answered truthfully, and returns the list to Bob.

Now, Bob must guess Alice's number.

What is the maximum probability that Bob correctly guesses Alice's number? (Assume that he chose an optimal set of 15 questions.)

Clarification: Bob may not ask self-referential questions (e.g. "Is your answer to this question a lie?"). No logical paradoxes, please! Questions asking about the truthfulness of answers to other questions are allowed.

×