Guess a number part 3. Alice is even lazier

Probability Level 3

Bob: Hey Alice, lets play "Guess a number"

Alice: Not again! Fine. This time why don't you tell me all your guesses at once.

Bob: Come on, where's the fun in that? The only way I can be sure to guess your number is if I guess all 10,000 numbers.

Alice: OK fine, two rounds and we'll only play to 500. You get one chance to submit a bunch of guesses, and I will respond to them. Then you must commit to a single number and if it is not my number you lose.

Bob: Hmm. That's still a bit absurd, but I'll play if you agree to a slight change of rules. Instead of guesses, I will give you a list of questions in the style of "Twenty Questions". You return my list with all my questions answered with "yes" or "no". Then I will commit to a single number. Deal?

Alice: Deal.


So Alice thinks of a number between 1 and 500.
Bob makes up a list of questions. Alice receives the list, answers all the 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?

Full disclosure: This problem was edited to improve correctness. Thank you to @Brian Moehring

Follow up to this problem

From Guessing games


Problem Loading...

Note Loading...

Set Loading...