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

The answer is 9.

2 solutions

Geoff Pilling
Nov 1, 2018

To clarify, each question asks about the nth bit of the binary reprentation of the number.

You mean the nth bit. :)

Incidentally, the word digit comes from the Latin word digitus meaning finger (of which you have ten)

Varsha Dani - 2 years, 7 months ago

Ah good point! ;)

Corrected

Geoff Pilling - 2 years, 7 months ago

Varsha Dani
Oct 30, 2018

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

To see that at least nine are needed, we note that even if you are allowed to ask questions adaptively, the best split of the possibilities you can hope for with a yes/no question is half-half. If you can halve (or nearly halve) the number of possibilities each time you need $\lceil\log_2 500\rceil$ or 9 questions to be left with only one possibility.

To see that 9 is actually enough even in the non-adaptive setting, we show a least of nine questions that determine the number:

Is your number even?
Is the floor of half your number even?
Is the floor of quarter your number even?
...
Is the floor of your number divided by 256 even?

Or, equivalently,

Is the units bit of your number zero?
Is the bit in the two's place of your number zero?
Is the bit in the four's place of your number zero?
...
Is the bit in the 256s place of your number zero?

Unless I am miscounting, you have asked 10 questions there.

Brian Moehring - 2 years, 7 months ago

Er, oops. you are right. Sorry about that. That's what comes of posting stuff late at night...

Now to work out how to change it...

Varsha Dani - 2 years, 7 months ago

@Brian Moehring Thank you for pointing out the mistake. I've updated the problem so it should be correct. It seems that you cannot change the answer, so I changed the question instead. Or would it be better to delete and repost? I still believe that it is a nice question, so I don't want to delete it altogether.

Varsha Dani - 2 years, 7 months ago

Nice problem, thanks, but how is the difficulty level of a problem determined (sorry I'm new to Brilliant)? I don't think this would be a "hard" problem for anyone who looked at the prior problems in the series. I'd say it's "medium" at most, and "easy" for anyone with programming experience.

Tapani Lindgren - 2 years, 7 months ago

I'm new to Brilliant as well (Been on about a month.) I have absolutely no idea how the difficulty level is determined. When I posted it it was "unrated" and a few days later it had auto-updated to "hard"

Varsha Dani - 2 years, 7 months ago

Yeah, I was originally thinking binary search.

Brian Bohan - 2 years, 7 months ago

Well, I'll just point out that the usual way of describing binary search is adaptive. After you've found out that 250 is too small, you say 375, but if it had been too big, you would say 125. That does not work here, because you have to ask all your questions at once. Indeed, if you had to make guesses that divide the interval, instead of asking arbitrary binary questions, then there is no way to accomplish this without guessing every number.

Varsha Dani - 2 years, 7 months ago

@Varsha Dani – True. testing the bits is the better way.. It's a really cool problem tbh.

Brian Bohan - 2 years, 7 months ago

Guess a number part 3. Alice is even lazier

The answer is 9.

2 solutions

0 pending reports