Guess a number part 4. Fill in the blank.
- Bob: "Hey, Alice!"
- Alice: "Yes, I know. You want to play 'Guess a Number.' I'll play the two-round version where you submit a list of yes/no questions, then I answer them, and then you guess one number."
- Bob: "Okay! So..."
- Alice: "But I will not answer all of your questions. I will leave one question (of my choosing) unanswered."
- Bob: "Oh..."
- Alice: "Still want to play?"
- Bob: "Yes!"
So, Alice thinks of a number between 1 and 1000, and Bob makes up a list of questions.
Alice then receives the list, selects one question to leave blank, answers all of the other questions with yes or no, and returns the list to Bob.
Now Bob must guess Alice's number and, if he is wrong, he loses.
How many questions does Bob need to ask (non-adaptively) in order to correctly identify Alice's number and guarantee a win?
- Follow up to this problem .
- From Guessing Games
The answer is 11.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
We know that it requires ⌈ lo g 2 1 0 0 0 ⌉ answered questions to identify a number between 1 and 1000 (and also that 10 are sufficient). Therefore if Alice leaves one question unanswered, clearly Bob needs to ask at least 11 questions.
Now for Bob's strategy. If he knew which question Alice would leave unanswered, he could simply ask it twice. But since he does not know which question Alice will not not answer, it may seem like he needs to ask each question twice, thereby needing 20 questions. However this is not the case. Here is how Bob can identify the number with only 11 questions.
Now if Alice answers Q1-Q10 and leaves Q11 blank, then Bob knows the number. Otherwise Alice leaves one of the questions about the bits in the representation blank, but this can be reconstructed using her answer to Q11.
This problem and strategy are related to Erasure Codes.