Unlock the safe!

Question

There is a (very insecure) safe, which has three digits in the lock. Each digit can only be $0,1,2$. The user choose a password made up with three $0,1,2$ digits, and the safe can be unlocked if at least two digits match the password at the exact position. How many tries at most to guarantee the opening of the safe?

---

From a primary math Olympiad problem. (I remembered that it was the last problem but forgot the competition.)

---

Bonus: How many tries at most to guarantee the knowledge of the original password?

Answer 1

I think the best we can do is

5 tries

The following tries will cover all possibilities

000
111
122
212
221

Proof that this is the best possible

Each try covers exactly 7 possibilities for the combination. Since there are 27 possible combinations this gives us a lower bound of four tries in the worst case scenario.
Additionally, to reach all combinations with four tries, three of the tries must have no mutual overlap in the combinations they cover.
Two tries have no overlap if and only if all three digits are different.
Therefore, without loss of generality, we can make the first three tries 000, 111 and 222.
But now we see it is impossible to cover the remaining possibilities with one additional try.

Alternative Proof (courtesy of Jaap Scherphuis in the comments)

With 5 or fewer guesses, there must be one that has a unique first digit by the pigeonhole principle. There are four codes that start with the same digit which are not covered by this guess. Your other guesses have a different first digit so would have to match both other digits to eliminate one of these codes, so you need at least four further guesses.

Bonus Not totally sure but the best I've managed to do is

8 tries

As follows

Suppose we make the guess 000 and it opens the safe.

Then we can find the exact combination in four more tries as follows.
Try 011, if it opens try 001 (opens means 001 is the combo, stays shut means it's 010).
If it stays shut on 011, try 022. If it opens, try 002 (opens again means 002 is the combo, stays shut means it's 020).
If it stays shut on 022, try 101. If it opens, the combination is 100.
If it stays shut again, try 201. If it opens, the combination is 200.
If it stays shut on 201 then the combination is 000.

We can form a similar sequence for any case where the safe opens. Using our original set of five guesses, if the safe opens for one of the first four guesses, we can use that as our starting point for the sequence above. If not, we know that 221 will open the safe so we don't need to try it but can use it as our starting point. So the maximum number of guesses needed is 4+4=8.

There seems to be some wiggle room here so it might be possible to reduce this to 7 but I'm not sure at the moment how to do it.

Answer 2

Pictorial analysis

There are $27$ different possibilities to enter into the lock. Let's say two of them are connected if they have two common digits (in the same positions); so every possibility is connected to exactly $6$ others. We can show them on a diagram like this:

The single-digit possibilities are shown in red, and the double-digit possibilities in green. Each single-digit possibility is connected to six double-digit ones around it. Each double-digit possibility is connected to one single-digit, one double-digit in red (same digit appearing twice), two double-digits in green (same two digits appearing), and two triple-digit possibilities (not shown on this diagram).

We can also see here that two triple-digit possibilities which are cycled versions of each other must be connected to two disjoint collections of double-digit possibilities:

So three cycled triple-digit possibilities are enough to connect to ALL the double-digit possibilities, but the single-digit possibilities are still separate. That means we could unlock the safe with

six tries: e.g. $012,201,120,000,111,222$.

But we can do even better by using the "middle" type of possibility: not triple and single, but use the double-digit ones that connect to both. Any trio of double-digit possibilities (we can see they're arranged into trios) will, between them, connect to ALL the triple-digit possibilities, and also to all the other double-digit possibilities which either use the same two digits or use the same digit twice, as well as of course one single-digit possibility. For example,

trying $100,010,001$ will cover all triple-digit possibilities and also $110,101,011$ and $002,020,200$ and $000$. Now the remaining double-digit possibilities are $112,121,211$ and $122,212,221$ and $022,202,220$ which are covered by $111$ and $222$.

So we can unlock the safe with

five tries: $100,010,001,111,222$.

Is it possible to do better?

No, see hexomino's answer. (I found this solution independently, but didn't get around to proving optimality before the other answer was posted. However, I still think it's worth having this answer for the pictorial approach which makes it seem natural.)

Bonus question

We know that every triple-digit possibility is connected to exactly one double-digit from each trio, and every double-digit possibility is connected to exactly two triple-digit possibilities which are not cycles of each other (and are therefore transpositions of each other). Each pair of transposed triple-digit possibilities has two different double-digit possibilities connected to the same pair (e.g. $012,102$ are both connected to both $112$ and $002$).

So we can manage to deduce the exact password with

8 tries: all the triple-digit possibilities and two of the single-digit ones. After trying all the triple-digit ones, we know that: if only one of them works, then that's the exact password; if exactly two of them work, then we have two double-digit possibilities for the password; if none of them work, then we have three single-digit possibilities. In either of the latter two cases, we can distinguish between remaining possibilities by trying two of the single-digit ones.