Bobby's booby-trapped safe requires an n-digit code to unlock it. Alex has a probe which can test combinations without typing them onto the safe. The probe responds Fail if no individual digit is the same as that in its corresponding position in Bobby's code. Otherwise it responds Close, including when all digits are correct. For example, when n=3, if the correct code is 014, then the responses to 099 and 014 are both Close, but the response to 140 is Fail.
Your task is to create a program/function that takes n (a positive integer) as input and returns the answer to the following question:
If Alex is following an optimal strategy, in the worst-case scenario, what is the smallest number of attempts needed to guarantee that he knows the correct code, whatever it is?
This is a codegolf challenge, so make your code short.
> 1 9 > 2 11 > 3 13 > 4 16 > 5 19 > 6 21
This is a modified version of a problem from BMO2 2017.
Explanation of the Test Cases
Where n=1, in the worst case, Alex will try eight numbers that all fail. The ninth number he tries will determine what the code is. Therefore, the answer is nine.
Where n=2, there are a hundred possible codes. In the worst case, he will fail the first test and narrow it down to eighty-one possible codes. Failing will be the worst case (and so he'll keep failing) until Alex has narrowed it down to nine possible codes (after seven tries). If he fails the next one (on his eighth try), he'll have narrowed it down to four possible codes, so if he gets 'Close', then he'll have five possible codes. We can then deduce that Alex will need at least three more tries to guess the code because five distinct numbers cannot be represented with distinct two-digit binary codes. Thus, Alex needs at least eleven guesses. Now, observe that Alex can find the code in eleven guesses. He can try 00, 11, ..., 99. If he failed nine of those tests, the one he didn't fail is the answer. If he failed eight of them (suppose he didn't fail xx and yy), he can try xy. If xy fails, the code is yx. Otherwise, the code is xy. Therefore, the answer is eleven.
Where n=3, Alex will fail every try (like in the n=2 case). He will start with a thousand possible codes, then after his seventh guess he will have narrowed it down to sixty-four possibilities (in the worst case, when Alex has failed all the tests). Then, if Alex doesn't fail the next test, he will have narrowed it down to thirty-seven possibilities. Alex will then need at least six more guesses to find the code. Therefore, Alex needs at least thirteen guesses. In fact, finding the code within thirteen guesses is possible. A possible strategy is to try 000, 111, ..., 999. If nine of these fail, then the code that didn't fail is right. If eight of them failed, then (if xxx and yyy worked and zzz failed) Alex can do xzz, zxz and zzx to check if each digit is x or y. If seven codes failed, then (if xxx, yyy and zzz worked and www failed) Alex can do xww and yww (to find the first digit) and then there is just one more code (could be xyz, xzy, yxz, yzx, zxy or zyx) Alex can try to see what order the last two digits are in (since the code has to be made of three different digits).
A similar argument is used for n=4, n=5 and n=6. Note that a different strategy would have to be found for n>10.