Cracking a combination lock

Question

Let's consider the humble mechanical combination lock. The basic type has $n$ dials, with $k$ digits on each dial, for a total of $k^n$ possible combinations. (Typical luggage locks or suitcase lock have $k=10$ and $n=3$ or $4$.)

These locks are usually cheaply made and quite simple to crack, as their mechanism "leaks" information to an attacker. For example, the lock might 'click' whenever a dial is rotated into the correct position, making opening the lock a simple matter of turning all of the dials until they click.

In this question, let's assume that the lock works like this:

• Set the dials to any desired position.
• Attempt to open the lock (by, e.g., pulling on the shackle).
• If all the dials are in the correct position, the lock opens; otherwise it remains closed.
• However, if one or more of the dials are in the correct position, the lock will "click" when the shackle is pulled. This gives us some extra information to work with.

What strategy should I use to minimize the worst-case number of attempts required to unlock the lock? Note:

• The initial starting position is random.
• Your strategy should be minimal for all $k\geq 2$ and $n\geq 1$, even cases where $n>k$.
• You must open your lock on the last attempt, even if you have figured out the combination without opening the lock.

This is equivalent to a game of Mastermind with $n$ pegs in $k$ colors, where the codemaker only has one red pin to respond with, and you wish to minimize the number of turns in which you are guaranteed a win.

Answer 1

Strategy for $n<k$:

1. Find the subset of digits being used by setting all dials to each digit at the same time and pulling. In the worst case, this takes $k$ moves and reduces $k$ to $n$.
2. Place the dials in a position they don't click (unused digit)
3. For each dial, try the used digits until one of them clicks or we reach the last one without having heard a click. Write down that digit. This takes in the worst case $n(k-1) = n(n-1)$ moves.
4. Once we know all digits, open the lock with $1$ more move.

The total number of moves is: $k + n(n-1) + 1 = n^2 - n + k + 1$

---

Strategy for $n \ge k$ (I doubt this the most efficient strategy):

1. Continuously increase the combination by one (treat dials as digits of a base k number), until you find a solution that doesn't click. The number of solutions that don't click is $(k-1)^n$ (all digits wrong), so the number of solutions that do click is $k^n - (k-1)^n$. In that many moves, we have either found the solution (one of the click-solutions is the final solution) or a non-click solution.
2. For each dial, try each digit one by one until you hear a click or the dial reaches the last one without clicking. Write that digit down. This takes $n(k-1)$ moves.
3. We know all digits, so we can open the lock with $1$ more move.

The total number of moves is: $k^n - (k-1)^n + n(k-1) + 1 = k^n - (k-1)^n + nk + 1$

Answer 2

Once you find a single combination that doesn't click, you can open the lock in $nk$ steps by taking $k$ steps to find each dial's correct position.

One way to find a nonclicking combination: try all $2^n$ combinations where each dial is set to either 0 or 1. One of these is sure to not produce a click. Therefore, $2^n + nk$ guesses is enough to crack the lock.

My current best strategy for $n > k > 2$ is to try combinations uniformly at random until you get one that doesn't click. This gives a bound of approximately (I think) $e^{n/k} \cdot n \log k$ for large $k$ and $n$. I won't write out all the details here, since (1) it's standard union bounding and (2) there's a good chance you can do better.

Answer 3

This strategy is not optimal for all the parameters, unless stated for some cases.
I tried to emphasize where to look for rooms for improvement.
I start with a trivial case, then another one which has a nice symmetry is described. Later you can find a method which is inspired by earlier answers, and improves them a little bit further. All these methods are easy to perform without heavy calculations or memorization. As a finish, I linked an answer which targets to answer the optimization of the original Mastermind thoroughly, and even though the idea works for this game as well, that one is basically a brute-force approach which needs a computer for (not even too) large $n$s and $k$s.

In some examples below, I mark digits with characters '0', '1', and so on. In case of multi-dial locks, (that is $n>1$), applicable combinations are marked with concatenation of $n$ of these characters, e.g. '063132', or even in a parametric way '(k-1)(k-1)...(k-1)'. To avoid ambiguity, parentheses are always used around non-single-character digits.

A trivial case: $n=1$

In this trivial case, you need $k$ attempts in the worst case.

There are $k$ possible combinations in total, $k-1$ of them which are non-clicking, and $1$ which opens the lock. There is no combination which produces a click.

This solution is optimal, that is you cannot find a better approach by going through the possible combinations in a clever order. You can always be so unlucky that the opening combination is the last one. Attempts don't give any information about which other combinations are more likely to open the lock: for example, if we have $k=10$, and the attempts '0' and '1' have failed as the first two attempts, '2' is just as good as a third attempt, as '7'.

A special case: $k=2$

This needs $2^{n-1}+1$ attempts in the worst case.

From all the possible $2^n$ combinations, there is obviously only $1$, which opens the lock. Also, there is only $1$ which is non-clicking - the one that is the inverse of the solution, that is, all its digits differ from the corresponding digit of the opening combination. All the other $2^n-2$ combinations are clicking.

To find the solution in $2^{n-1}+1$ moves, we can use this pairing of the combinations: two combinations are paired, if they are inverses of each other. From every pair, you have to try only one of the combinations in the pair - the result of the attempt gives you full information about what the result were in case you attempted the inverse combination.
Take those combinations which all start with '0'. This is a set of combinations which all contain one combination from all the pairs defined above. There are $2^{n-1}$ of them, all but one producing a click, while one of them is either a non-click, or an opening combination. Just it was in the first case, a failed attempt does not give any non-trivial information about the solution, so there is no clever ordering of the combinations for the next attempt. Again, if you are unlucky, the last attempt will be the one which is not a click. Furthermore, if it was not an open, but a non-click, you need one more attempt to open the lock with its inverse. This solution is optimal too.

A general method

@Lopsy's idea can be further enhanced trivially. With $2^n+n(k-2)$ attempts it is always possible to open the lock.

I won't really use these numbers in the following calculations, but just to have a complete enumeration: out of the $k^n$ possible combinations, there is exactly $1$, which opens the lock; ${(k-1)}^n$ are non-clicking; and the rest: $k^n-{(k-1)}^n-1$ is clicking.

As already suggested by Lopsy, take those $2^n$ combinations whose every digit is a '0' or a '1'. If none of these open the lock, then at least $2$ of them results in a non-click (because at least one digit of the opening combination is neither '0' nor '1'). This means, that we've found a non-clicking combination in $2^n-1$ attempts. So we know one non-clicking digit on each dial. Working dial by dial, we need at most $k-2$ further attempts to figure out the clicking digit on each of them: if none of the other $k-2$ digits click on that dial, the last, unattempted one will. That's another $n(k-2)$ attempts after finding the first non-clicking combination. A last attempt is needed to actually open the lock, so we made $2^n+n(k-2)$ attempts in total.

This method leaves a lot of room for further optimization. First of all, reordering the first $2^n$ attempts can ensure you find a non-clicking combination a few attempts earlier. Also, what are the different scenarios during the search for the first non-clicking combination?

• If we find a non-clicking combination much earlier than $2^n$ attempts, we have ruled out the term which was responsible for the order of magnitude of steps.

• If we need many attempts to find the first non-clicking combination, then those early attempts - if done cleverly - may give some information about a few digits.

These are only intuitive remarks, not rigorous observations. For me it seems, at least around $2^n$ attempt is needed in these cases anyway, but maybe the additional $n(k-2)$ can be lowered.

Of course if $n$ and $k$ fulfill some other property, there can be specific strategies applied.
Such one is the case of $n<k$, for which a strategy was already suggested by @Runemoro.

Finding the subset of digits being used takes $k$ attempts in the worst case indeed.
However, after this his idea can be further improved I think, if we don't progress dial-by-dial, but digit-by-digit.
Because of symmetry, we can assume the digits being used are '0', '1', ... 'm', for some $m{\le}n$.
Finding all the dials on which '0' appears, needs $n$ attempts at most (or one less, if none of the first $n-1$ attempts were clicking), and leaves us with $n-1$ unidentified dials at most (or less, if '0' appears more than once on the opening combination).
After that we go through all the dials for digit '1', but this needs $n-1$ attempts at most, as we have less unidentified dials left.
Iteratively, the last digit we have to look for is '(m-1)'. There are at most $n-m+1$ unidentified dials left before we do this, and when we finish, we can know, that all the dials left unidentified have 'm' in the opening combination.
If $m=n$, then we can save at least one attempt in all these turns (if we don't have a click before the last dial is attempted, we can know it is that one without attempting).
So we might give the rough upper estimate for this digit-by-digit search: it needs at most $n+(n-1)+\dots+(n-m+1){\le}n+(n-1)+\dots+2=\frac{n(n+1)}2-1$ attempts.
The total number of attempts needed - identifying the used digits, identifying their places, and finally opening the lock - is $k+\frac{n(n+1)}2$ altogether.
This improves Runemoro's method if $n>2$, and even for $n\le2$ it gives the same number of attempts.

Optimal solution

As it was already mentioned in the question, this is a special version of Mastermind. With the needed modifications, the idea behind the method described in this comprehensive answer about how to excel in the original game answers your original question.
However, for me it seems it is computationally heavy to keep tracking which next attempt gives the optimal partitioning of the yet-possible answers, even if you use a greedy minmax approach. The methods listed previously were all possible to execute by hand and maybe using some pen and paper.