6
$\begingroup$

I'm thinking of a 2-digit secret number XY, where X is the first digit (non-zero) and Y is the second digit. You can make guesses to find it. If your guess is correct then the game finishes. Otherwise after a guess AB, I will tell you the result of $|A-X|+|B-Y|$. What is the minimum number of guesses you need to guarantee finding the secret number?

$\endgroup$

1 Answer 1

7
$\begingroup$

I can do it in

three guesses. Two to determine the number, and then the third to finish the game.

The first guess is

$99$, and then the second guess is $90$.
Let the answers to these guesses be $d_1$ and $d_2$ respectively.
We have
$d_1=|9-A|+|9-B|= 18-A-B$
$d_2=|9-A|+|B|= 9-A+B$
From these two equations we can always deduce the two variables $A$ and $B$. In particular, $d_1-d_2=|9-B|-|B|= 9-2B$ allows you to determine $B$. Once you know $B$, you can substitute it in either equation to get $A$ itself.

For example, if the answers were $d_1=7$ and $d_2=6$, then $9-2B=7-6$ gives $B=4$, and then $6=9-A+4$ gives $A=7$.

The reason this works is that the two guesses are in adjacent corners of the rectangular search space. Only for those points are the signs of $A-X$ and $B-Y$ known regardless of the values of $A,B$. With any other points the absolute value signs would allow multiple possibilities, and then the two equations would not always have a unique solution. Of course any pair of adjacent corners could be used: $(10,19)$, $(90,99)$, $(10,90)$, or $(19,99)$.

As 2012rcampion points out in their answer, it is impossible to do it in fewer guesses. The result given is a whole number in the range $[1,18]$, so cannot dstinguish between all $89$ unguessed numbers.

$\endgroup$
1
  • $\begingroup$ Correct and well done! $\endgroup$ Jul 4 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.