We are going to play a regular “find my number” game, i.e. you announce your initial guess and following my answer ( limited to: “more “, “less” or “right!”) go on to your next guess.
Usually to reveal a number from 1 to N you need no more than log₂N guesses in the worst case.

How many guesses are needed if I told you that my number is a 4-digit palindrome divisible by 7 ?

Assume the worst case, of course.

First, note that there are 18 such integers, of the form abba, where a is any digit from 1 to 9, and b can be either 0 or 7.
Also note that if there are an odd number, 2n+1, remaining, I can choose the one in the middle and eliminate n+1 with n remaining, so I can eliminate slightly more than 1/2 the options.  This is because there are 3 possible answers, "right" being one of them.
So even though log(18,2) is about 4.17, I can do this in 4 guesses:
Guess 5775, "less"
Eliminate 9, there are 9 remaining
Guess 3003, "less"
Eliminate 5, there are 4 remaining
Guess 2002, "less"
Eliminate 2, there are 2 remaining
Guess 1771, "less"
Eliminate 1, 1001 is the solution
The answer is 4 guesses.

Posted by Larry on 2023-05-15 07:15:10