BMO2 2017 Question 4 - Bobby's Safe Bobby’s booby-trapped safe requires a $3$-digit code to unlock it. Alex
has a probe which can test combinations without typing them on
the safe. The probe responds Fail if no individual digit is correct.
Otherwise it responds Close, including when all digits are correct. For
example, if the correct code is $014$, then the responses to $099$ and $014$
are both Close, but the response to $140$ is Fail. If Alex is following an optimal strategy, what is the smallest number of attempts needed to
guarantee that he knows the correct code, whatever it is?
I think the optimal number is $13$ (start by trying $000$, $111$, $\ldots$, $999$), but it's hard to find bounds here. Any help?
 A: 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\,.$$
