38
$\begingroup$

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:

a rendered picture of a three decimal digit lock

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.

$\endgroup$
  • 2
    $\begingroup$ Does "best strategy" mean fewest guesses, least movement of the wheels, or some other criterion? $\endgroup$ – David K Oct 25 '16 at 17:32
  • 7
    $\begingroup$ Further clarification: fewest guesses on average? or fewest guesses in worst case scenario? $\endgroup$ – JMoravitz Oct 25 '16 at 17:35
  • 1
    $\begingroup$ It seems the "specialty" in this lock reduces the guess space from 1000 to 300. The brute froce way would be to ignore one digit and try 99 combinations with the other two and repeat three times. $\endgroup$ – darksky Oct 25 '16 at 17:37
  • 4
    $\begingroup$ @darksky But if you go through all 100 combinations of two digits, then for one of those the lock should open. So why is it not 100? Why 300? $\endgroup$ – Bram28 Oct 25 '16 at 17:40
  • 1
    $\begingroup$ So: the optimal strategy is ... whatever you try next, try and have it something that has at least two digits different from all the things you already tried ... and do that in a sequential way so that you can make sure there is a new number that has a 'two_digit_different_distance' from all tried numbers as many times as possible? ... $\endgroup$ – Bram28 Oct 25 '16 at 18:12
25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice! Beats my strategy! +1! A proof would seem to be difficult though, no? $\endgroup$ – Bram28 Oct 25 '16 at 23:26
  • $\begingroup$ Beats my strategy. $\endgroup$ – fleablood Oct 25 '16 at 23:28
  • $\begingroup$ Do you think you can get it down to 45 of by doing 011 to 099, then 101-180 , 202-270, etc.? Just taking a wild guess. $\endgroup$ – fleablood Oct 25 '16 at 23:44
  • $\begingroup$ The average trails is calculated by computer or by hand? $\endgroup$ – fizis Oct 26 '16 at 2:14
  • 1
    $\begingroup$ @fleablood The claim that 50 is the smallest possible number has been repeated in peer-reviewed mathematical literature since 1969, so I don't expect to go below that. :) And I don't know how to interpret "101-180": going 101, 112, 123, ... would end in 189 and 190, not 810, and I see no other obvious continuation. $\endgroup$ – JiK Oct 26 '16 at 9:06
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ worse case scenario is no better than fixing the first digit and guessing the other two. $\endgroup$ – fleablood Oct 25 '16 at 18:32
  • $\begingroup$ True. No matter what method, worst case is always 100 tries. But I think this method optimizes average number of tries $\endgroup$ – Bram28 Oct 25 '16 at 18:36
  • $\begingroup$ That seems to be a good strategy $\endgroup$ – Djura Marinkov Oct 25 '16 at 18:53
  • $\begingroup$ Why not just 000 to 009, then 110 to 119, then 220 to 229, etc? This seems to capture the essence of your strategy but more simply. $\endgroup$ – Wildcard Oct 25 '16 at 19:09
  • 1
    $\begingroup$ Strange that a guess that seems suboptimal and doesn't even contain a sketch of a proof would be the top answer. -1 $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 25 '16 at 23:01
1
$\begingroup$

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 :)

$\endgroup$
  • 2
    $\begingroup$ But it is not clear that if for every new number you pick, you pick the one that discriminates the most number of combinations, that then you get the minimal number of guesses on average. For example, maybe by picking a combination that discriminates 10 other combinations (as opposed to one that discriminates only 9), I am being 'locally greedy', and the best subsequent move may only be able to discriminate 6 (for a total of 16 between the two moves), while the other move has a subsequent move that discriminates 8 (for a total of 17 between the two moves). $\endgroup$ – Bram28 Oct 25 '16 at 18:23
  • $\begingroup$ @Bram28 you are right, it is possible that in a moment, maybe, the better probability in the next try doesn't mean better strategy in total. It should be taken care in the late moves, when numbers are low and divisibility is matter. $\endgroup$ – Djura Marinkov Oct 25 '16 at 18:31
  • $\begingroup$ At least this establishes a lower bound on the worst-case number of tries. You cannot "cover" more than $28$ combinations per try, so it will take at least $\lceil 1000/28 \rceil = 36$ tries. $\endgroup$ – David K Oct 25 '16 at 19:26
  • $\begingroup$ I think theoretically this might be a right direction. $\endgroup$ – fizis Oct 26 '16 at 1:30
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.