Guess a number part 2. Alice is lazy

Probability Level 4

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

Alice: Oh I couldn't be bothered...

Bob: Oh come on, please?

Alice: Fine, I'll play. But you must submit your guesses in batches of 4. Except at the end. On your last attempt you can guess just one number, but if you are wrong you lose.

Bob: Oh, OK. But what will you tell me about my guesses when I make 4 at once?

Alice: The usual. Whether each one is too small, too big, or correct. Tell you what, I'll make it a bit easier. I'll choose a number between 1 and 6249.

%%%

So Alice thinks of a number between 1 and 6249.
Bob may play as many rounds of guessing four numbers as he wishes. [Note: the four guesses need not be distinct, but they will count for four guesses]. On the final round he must commit to a single number that he believes is Alice's number.

How many guesses does Bob need in order to correctly identify Alice's number and guarantee a win?

Remember, your answer must be 1 mod 4.

Follow up to this problem

From Guessing games

The answer is 21.

1 solution

Geoff Pilling
Oct 30, 2018

Each time you make 4 guesses, your optimal approach is to divide the region into 5 equal parts with your guesses.

So, the number of turns you need is given by the recursive relation $a_0 = 1$ , and $a_n = 5a_{n-1} + 4$ for $a>0$ .

So, $a_5 = 6249$ .

Since there are 4 guesses each turn, and one final guess:

$N = 4 \cdot 5 + 1 = \boxed{21}$

Doesn't Bob need 20 guesses at the most in order to provide the correct answer in round six? What does "your answer must be 1 mod 4" mean? I'm sorry if I'm being a bit obtuse.

Mick Petzold - 2 years, 7 months ago

Varsha is including the final guess. Thus the 1 mod 4.

i.e. the answer should include all of the "4 guesses" +1.

Geoff Pilling - 2 years, 7 months ago

Guess a number part 2. Alice is lazy

The answer is 21.

1 solution

0 pending reports