Best strategy to pick a lock which opens if at least two of its three decimal digit wheels are dialed correctly?

Question

Suppose you want to open a lock with three digits code, the lock is a little special because it can be opened if you have two digits guessed right. To clarify, if the correct three digit is 123, then guess 124 or 153 can open the box. The lock looks like this:

Question is: what is best strategy to open the box? The best strategy is a strategy which requires least attempts at average. You should also find the average.

The strategies I came up with are:

First strategy: hold first digit, and constantly change second and third while keep them equal when changing them. For example, I will try: 111, 122...199,211,222,...,299,....

Second strategy: hold second and third equal, and constantly change first one. For example: 111, 211,...,911,122,222,...

I don't know if these two are best, nor do I know if they are equivalent efficient.

Edit

Here is a program to calculate the average number of trails for a strategy from an ardent comment. To use it, replace the line '// Input your list here' with your test list and press run.

Answer 1

I have a strategy with at most $50$ tries and $22449/1000=22.449$ expected tries.

$$ \begin{align} 443, 796, 869, 101, 230, 577, 314, 022, 965, 656, \\ 588, 757, 875, 213, 140, 331, 689, 998, 404, 410, \\ 134, 303, 241, 886, 555, 667, 779, 421, 599, 000, \\ 432, 202, 897, 768, 044, 033, 695, 342, 011, 976, \\ 678, 959, 112, 858, 987, 224, 123, 320, 566, 785\phantom{,} \end{align} $$

This was obtained by starting from the unordered set of these words (given by a covering code) and then ordering them using a greedy computer search; more details below.

---

First, I'll get some ideas by considering another problem, optimizing the number of tries needed for the worst case, which has a known solution for this case. A covering code $C$ with alphabet size $q=10$, length $n=3$, and covering radius $R=1$ is a set of $3$-tuples (called words) of length $3$ over $\{0,1,\dots,9\}$ such that every possible $3$-tuple differs from one in $C$ in at most one position. This is exactly what we need.

The minimal size with these parameters is $50$ [1]. It contains these words: $$ \begin{array}{|ccccc|} \hline 000 & 011 & 022 & 033 & 044 \\ 101 & 112 & 123 & 134 & 140 \\ 202 & 213 & 224 & 230 & 241 \\ 303 & 314 & 320 & 331 & 342 \\ 404 & 410 & 421 & 432 & 443 \\ \hline 555 & 566 & 577 & 588 & 599 \\ 656 & 667 & 678 & 689 & 695 \\ 757 & 768 & 779 & 785 & 796 \\ 858 & 869 & 875 & 886 & 897 \\ 959 & 965 & 976 & 987 & 998 \\ \hline \end{array} $$

For any two columns, the upper half contains a word for all $25$ pairs of symbols in $\{0,1,2,3,4\}$ that can occur there, and the lower half contains all $25$ pairs of symbols in $\{5,6,7,8,9\}$ that can occur there. The correct combination has to contain at least two symbols from either set, so it is opened by entering one of these words.

[1] Some sources refer to "J. G. Kalbfleisch and R. G. Stanton, A combinatorial theorem of matching, J. London Math. Soc. (1), 44 (1969), 60–64; and (2), 1 (1969), 398", but I can't find the paper. However, the value is listed in the fourth PDF listed at the top of this page by Gerzson Kéri.

---

Now back to the original problem, optimizing the expected number of tries required. My idea is to try to take these words and optimize the order somehow. This of course doesn't guarantee that we have an optimal solution.

I tried a greedy random approach: Choose words one by one. At each step, for each possible new word $c$, find the number of previously uncovered words that would be covered by $c$. Then among the ones that cover the most, choose one by random. After some time, the best that I could find was the order given at the top of this answer, with $22449/1000$ as the expected number.

Answer 2

OK, so the basic idea I have is as follows:

We want to cover as many possible combinations as possible for each try. Thus, for example, the OP's strategy of doing 111,122,..., followed by 211,222, ... would seem less than optimal, since the first 10 tries already cover any combinations with the last two digits being the same. So, it would be better to do 111,122, ... followed by something like 223,234,245, so that not only do you try to get a hit between the first digit and any of the other two, but you are also trying other options to get a hit between the 2nd and 3rd digit.

In fact, even 111,122,... is less than optimal, since they both cover 121, so you get overlap. So, it's probably best to start with something like 111,222,333,... since each of these covers 28 combinations without overlap.

After that, I figure we should just keep making sure that every new try we make has as few digits in common with whatever combinations we already tried up to that point... basically try and make each combination differ in 2 digits from any of the ones tried before. The following sequence will do exactly that (each sequence of 10 has a unique difference between 1st and 2nd digit, between 2nd and 3rd, and between 1st and 3rd):

000, 111, 222, 333, ..., 999, (at this point we have covered 10*28=280 combinations)

012, 123, 234, 345, ..., 901, (another 10 * 22 (e.g. 012 covers itself and 3*7 more) = 220)

(so with a mere 20 tries we cover half of all possible combinations!)

024, 135, 246, 357, ..., 913, (another 10 * 18 (this takes some writing out) = 180)

036, 147, 258, 369, ..., 925, (another 10 * 12 = 120)

048, 159, 260, 371, ..., 937, (another 10 * 8 = 80)

(at this point, don't proceed with 050,... since that has two digits in common with earlier 000)

051, 162, 273, 384, ..., 940, (another 10 * 5 = 50)

063, 174, 285, 396, ..., 952, (another 10 * 4 = 40)

075, 186, 297, 308, ..., 964, (another 10 * 2 = 20)

087, 198, 209, 310, ... ,976 (the last 10)

In an earlier version of my answer I said to do another 10 after these:

099, 100, 211, 322, ... , 988

the idea being that this would cover all possible pairs of 1st and 2nd digit, and thus covering all possible combinations (and thus we would have a worst case of 100). However, it turns out that whichever ones these additional 10 would cover have been covered already by the previous 90. So, worst case of this method is 90 tries, not 100.

The above method gives an average of 0.28*5.5 (the first 10 tries each cover 28 cases, so that is 280 cases out of 1000 is 28%, which on average take (1 + 10)/2 = 5.5 tries) + 0.22*15.5 + 0.18*25.5 + 0.12*35.5 + 0.08*45.5 + 0.05*55.5 + 0.04*65.5 + 0.02*75.5 + 0.01*85.5 = 25.2 tries to open the box.

I really think this method cannot be improved in terms of average number of tries, but I have no proof.

Edit ok, so this is not the most efficient strategy: see JiK's answer! Time to eat humble pie! ... Well, I hope at least I was able to express some of the ideas why some strategies might be better than others.

Answer 3

This is a problem with entropy, in each try you want to maximally lowerize the entropy.

Since I forgot the formulas for entropy I'll go this way... Maximize the probability to unlock in each try.(it's kinda same)

Let n be order of the try and p(n) probability to unlock, then:

$p(1)=\frac{3*9+1}{1000}=\frac{28}{1000}$

After first try you discriminate 28 combinations, so if you failed with 111, you also know that 112,113,...,121,... are not the combination

Lets try your second strategy for the next try, if you pick 211, you will discriminate another 18 combinations (212,213,...210,221,231,...230 but combinations 311,411... you already discriminated, so p(2) with the 2nd strategy is $p(2)=\frac{18}{972}$

Lets try 1st strategy, so second pick to be 122, this way you discriminate another 26 combinations cos 121 and 112 were already disc.

So I would decide for strategy to change all three digits, to discriminate another 28 combinations, so $p(2)=\frac{28}{972}$

That's what would you do for the first 10 tries, and for the rest... try on your own :)

Answer 4

So, what if you reduced the question to just 3 possible numbers allowed for each digit?

From $000$ to $222$

In that case, you can cover any of the 27 permutations with just 6 guesses $$000$$ $$111$$ $$222$$ $$010$$ $$020$$ $$101$$

So that's 6 guesses to get $3^3$. I'm not sure how this would generalize though.

Is it $n^2\frac{n-1}{n}=n(n-1)$ which would be 90 in your problem? (This generalization also works for the near-trivial example of only 2 numbers, 0 and 1, in which case 000 and 111 covers any permutation)

Also, this method is trying to minimize worst case, exhaustive method, not the average number of tries.

Edit: Confirmed $n(n-1)$ also covers every options in base 4 (from 000 to 333).

000, 111, 222, 333,

012, 013, 021,

102, 103, 120,

210,

301

And from what I gather from brute force methods, in your original question, cycling through the 000, 111, 222, 333....999 will take out 28 permutations each, for 280. After that, you will be able to make 80 guesses that will take out 9 permutations each, for a total of 90 guesses that cover all 1000 permutations.

Also, after 29 guesses, you've taken out over 500 of the permutations.

Answer 5

1) 000: Rules out more than 1 zero

2-4) 011;101;110: Rules out one and zero and more than one 1

25-28) 022;202;220;....099;909;990: Rules out 0 and more than 1 of any number.

29-34) 123,213,231,132,312,321: Rules any two of 1,2,3

35-52)145...167...189: Rules out any 1s; and any pair of (4,5)(6,7),(89)

53-58)246....642: Rules out 2s with 4or 6 and any pair of 4 or 6.

59-64) 257....752: Rules out 2s with 5 or 7; so only 2s with 8 or 9 are left. But 8 and 9 can't pair so this is impossible so, rules out 2s.

65- 70)347...743: Rules out 3s with anything less than 5s.

71-76) 356..653: Rules out 3s with anything other than 8 and 9, which is impossible so rules out 3.

4s are only possible with 8 and 9 so that's impossible.

6s are only possible with 8 and 9. 7 is only possible with 8 or 9.

So any combination we would have guessed in 76 guesses.

I'm not sure how to generalize.