Bobby's Booby-Trapped Safe

Question

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.

Test Cases

> 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.

Answer 1

Mathematica, 125 bytes (121 chars)

(f@{_}=0;f@l_:=1+Min[Max[{g=GatherBy[l,vFreeQ[#-v,0]]}~With~If[Length@g<2,∞,f/@g]]&/@R~T~#];f@(T=Tuples)[R=Range@10,#])&

Try it online!

(it actually does not run the code, just the function pasted into TIO. So because the function is not invoked, it does nothing)

This cannot be run even with input n=1 because it has no memoization or whatever optimization. The ungolfed code below, however, does return 9 for n=1.

Ungolfed code:

n = Input[];

base = 10;

Clear@f;
f@{_} = 0;
f@l_ := f@l =
  1 + Min[
    Max[
       With[{groups = GatherBy[l, v \[Function] FreeQ[# - v, 0]]},
        If[Length@groups == 1, Infinity, f /@ groups]
        ]
       ] & /@ Tuples[Range@base, n]
    ]

f@Tuples[Range@base, n]

This code run in upper bound time O(2^(10^n poly(n))), which is impractical for all n ≥ 2.

Explanation:

Let a number be represented as a list of n numbers from 1 to 10. There are 10^n numbers.
Then, the function f receive a list of "numbers" l (so a 2D list of digits), and return the information "assuming all the possible candidate numbers are in the list l, at least how many question are necessary to reduce it to 1 candidate in the worst case?"
So the function f is defined as:

f@{_} = 0;

When there is only 1 candidate, we only need to ask 0 more questions.

f@l_ := f@l =

Memoization (in ungolfed code) to slightly improve performance.

1 + 

Ask one question.

/@ Tuples[Range@base, n]

For each possible number (numbers are represent as n-tuple of digits, each digit is in the range from 1 to base (10)) to be asked,

Min[]

find the minimum (best strategy)

groups = GatherBy[l, v \[Function] FreeQ[# - v, 0]]

partition the candidates to 2 groups: one gives the value "Close" when ask this number, and the other gives the value "Fail" when ask this number.

If[Length@groups == 1,

If all the numbers in the list l get to the same answer when test,

Infinity

return Infinity (avoid asking this question, avoid loop forever)

, f /@ groups

otherwise recursively apply the function f to the resulting group

Max[]

and get the maximum (worst case).