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