8
$\begingroup$

There are $N$ letters in an alphabet. There is a combination lock, the code to it consists from $M$ different letters.

You can input $M$ letters combination and try to open the lock. (But you can't check the lock unless you have inputted all $M$ letters).

If you guess at least $M-1$ letters from the code correctly the lock will be opened. The order of letters does not matter.

How many tries you need to guarantee that lock will be opened? How to find list of combinations you need to try?

P.S. I am especially interested for the case $N=32, M=4$.

Here is an example for the case $N=4, M=3$. The alphabet is "ABCD".
The answer is 1, with working combination "ABC". Indeed, if the code is different it can be different in $1$ letter only, therefore $M-1=2$ letters are always the same.

Improve this question
$\endgroup$
9
  • $\begingroup$ Well, for $N=2$ and certain values of $M$, Hamming codes should produce an optimal strategy. Every possible combination is either a valid message or 1 bit off from exactly one valid message, so you get the maximum possible use out of every attempt. I'm not sure whether Hamming codes generalize to non-binary alphabets or whether it's possible to improve on truncated Hamming codes for values of $M$ that don't fit the Hamming code construction. $\endgroup$
    – user2357112
    Commented Jun 14, 2014 at 19:00
  • 2
    $\begingroup$ $M$ different letters, right. $\endgroup$
    – user2357112
    Commented Jun 14, 2014 at 19:33
  • 1
    $\begingroup$ Do you have to guess exactly $M-1$ letters, or will an exact match also open the lock? $\endgroup$
    – user88
    Commented Jun 14, 2014 at 19:37
  • 1
    $\begingroup$ The simple calculation is that there are $N \choose M$ codes, and each time you try $(N-M)(M-1)+1$ of them. You can divide these and round up to find a lower bound for the number of tries. The hard part is to find the combinations to try. It may not be possible to achieve the lower bound. $\endgroup$
    – Ross Millikan
    Commented Jun 15, 2014 at 17:46
  • 1
    $\begingroup$ @kaine: Slight correction, it should be $(N-M)M+1$. The codes you are checking are created by choosing one of $M$ letters to change. You have $N-M$ letters to change it to. Add the exact code you enter. I don't think there is a binary case, as you have to select the letters without replacement and order doesn't matter. $\endgroup$
    – Ross Millikan
    Commented Jun 17, 2014 at 17:00

1 Answer 1

Reset to default
1
$\begingroup$

I arrived at a relatively simple answer which assumes that one is not "clever" about cutting down the search space with strategic guesses. I'll discuss that a little more at the end.

The probability of choosing a winning combination is:

$( {M \choose M} + {M \choose M-1} )/ {N \choose M}$

i.e. The sum of either choosing all the numbers correctly and choosing all but one correctly. For your little example, this is $(1 + 3)/4 = 1$ - so you're guaranteed to win.

So, to answer the question itself, you would need to exhaust all the non-winning combinations first then the next one wins i.e. : ${N \choose M} - ( {M \choose M} + {M \choose M-1} )+1$ minimum attempts to guarantee unlocking.

Now, your challenge is essentially the game Mastermind where N is the number of colours and M is the length of the code (with no repeats) and a win only requires M-1 (or M) pegs of any colour. The cumulative efforts of the world's minds have not come up with a neat formula for this, but Knuth came up with a 5-move strategy for standard Mastermind.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn't the assume the non-winning combinations are unrelated? What if knowing that some set of combinations are all non-winning allows you to know that some other combinations you haven't yet tried won't win either? $\endgroup$
    – Ben Aaronson
    Commented Oct 6, 2014 at 20:29
  • $\begingroup$ You're right... thank you. I have added more. $\endgroup$
    – d'alar'cop
    Commented Oct 6, 2014 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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