BMO2 2017 Question 4 - Bobby's Safe
We shall first prove that the task requires at least $13$ attempts. In the worst case scenario, Alex's first six attempts all fail, which means he has at least $(10-6)^3=64$ remaining combinations to guess. If he gets a "Close" outcome in the seventh round, he will then have at least $$9+9+9+3+3+3+1=37$$ possibilities for the correct code. This means he will need at least $\left\lceil\log_2(37)\right\rceil=6$ more rounds, whence Alex cannot complete the task in fewer than $13$ trials.
We now claim that $13$ trials suffice. For the first ten tries, Alex takes the guesses $000$, $111$, $222$, $\ldots$, $999$.
- If he gets nine failed attempts, then the only one that gets the "Close" outcome is the correct code.
- Suppose for the moment that Alex gets exactly two "Close" outcomes $aaa$ and $bbb$. Then, pick a combination $ccc$ known to fail. Test $acc$, $cac$, and $cca$ to see which digit is $a$ and which is $b$.
- Finally, assume that Alex gets three "Close" outcomes $aaa$, $bbb$, and $ccc$. Then, there are six possibilities left $abc$, $acb$, $bac$, $bca$, and $cab$. Alex can guess $add$ and $bdd$, where $ddd$ is an already known failed guess. This will establish the first digit of the combination. Without loss of generality, the first digit is now known to be $a$. There are only two possibilities left: $abc$ and $acb$. Take the guess $dbc$. If this results in a fail, then $acb$ is the correct combination; otherwise, $abc$ is the correct combination.
Let $M(n)$ denote the minimum number of attempts guaranteed to crack the digit code of length $n\in\mathbb{Z}_{>0}$. Then, we obviously have $M(1)=9$, $M(2)=11$, and $M(3)=13$. Indeed, $$M(n) \geq \max\Big\{\big\lceil n\,\log_2(10-k)\big\rceil +k\,\Big|\,k\in\{0,1,2,\ldots,9\}\Big\}=:m(n)\,.$$ We see that $m(1)=9$, $m(2)=11$, $m(3)=12$, $m(4)= 15$, $m(5)= 18$, $m(6)= 21$, $m(7)= 24$, and for $n\geq 8$, $$m(n)= \big\lceil n\,\log_2(10)\big\rceil\,.$$ I believe that the inequality $M(n)\geq m(n)$ is not sharp for all $n\geq 4$. I struggled to find, for example, a $15$-step strategy for the case where $n=4$, and I conjecture that $$M(4)=16\,.$$