Suppose you have a lock of this sort that has n dials and k numbers on each dial. Let m(n, k) be the minimum number of turns that always suffice to open the lock from any starting position, where a turn consists of rotating any number of adjacent rings by one place.
In the previous post, we found an algorithm for computing these bicycle lock numbers, revealing a mysterious symmetry, which you can see in this table of values of m(n, k).
It looks as though m(a, b+1) = m(b, a+1) for all positive integers a and b. Also I verified this by computer for the first ten million rows of the table, so it seems plausible that it’s generally true.
On the face of it this is quite mysterious. For example, why can a lock with 4 dials of 10 numbers each – like the one pictured above – always be unlocked in the same number of turns as a lock that has 10 dials with 5 numbers each? The connection between the (4, 10)-lock and the (10, 5)-lock is not very obvious: one has 104 = 10,000 combinations and the other has 510 = 9,765,625 combinations.
The mystery solved
Anyway, it turns out that there is a simple connection, if you think about it in the right way. The overall plan is this: although an (a, b+1) and a (b, a+1)-lock generally have very different numbers of combinations (e.g. ten thousand versus almost ten million, as above), we can group together “equivalent” combinations in such a way that:
- Equivalent combinations need the same number of turns to unlock.
- there is a natural bijection between the equivalence classes of combinations of the (a, b+1)-lock and the equivalence classes of combinations of the (b, a+1)-lock.
So we’re going to progressively discard extraneous information about the combination – information that doesn’t affect the number of turns needed to open the lock starting from that combination – till we find the symmetrical core.
As before, we’re going to assume throughout that the destination combination, that opens the (n, k)-lock, is n zeros.
The first trick is one we used last time: instead of looking at the positions of the dials, look at the differences between the positions of adjacent dials. On its own this doesn’t discard any information – the process is reversible – but it opens the door to a nice initial simplification: the order of the differences doesn’t matter.
Here’s an example, for the (4, 10)-lock. Take the combination
0136, which has differences
01234. Using the technique from last time, we see that 0+1+2+3+4 = 1×10, so we add the smallest 5-1 = 4 of the differences, and the number of turns needed to open the lock is 0+1+2+3 = 6. If the differences were reordered, say as
30142, the number of turns needed would be the same, and the corresponding starting lock combination would be
3348. Reordering the differences establishes an equivalence relation on combinations according to which
0136 is equivalent to
3348 for the (4, 10)-lock, and equivalent combinations always take the same number of turns to open. From now on we’ll write the sequence of differences in nondecreasing order.
To motivate the next identification we’re going to make, let’s consider another example combination of the (4, 10)-lock:
2593 with differences
23447. This time the differences sum to 2×10, which means we can ignore the two largest differences and add up the others, so this combination takes 2+3+4 = 9 turns to open. But, since the two largest differences didn’t even enter into the calculation, they could have been any pair of numbers that are both at least 4 and sum to 11. In this case, of course, there’s only one other possibility: they could have been 5 and 6 so that the differences were
23456. The combination
2594 has these differences, so in this sense the combinations
2594 are also equivalent. We shall denote this equivalence class, naturally enough, by the sequence (2,3,4), the initial segment of the nondecreasing sequence of differences that sums to the number of turns needed. We’ll call that a lock sequence for the (4, 10)-lock.
Is there room in the attic for all the boxes?
Now let’s characterise the lock sequences.
Let d1, d2, …, dm be a nondecreasing sequence of natural numbers less than k having length m ≤ n; this is a lock sequence for the (n, k)-lock if
which simplifies to
The first inequality is a bit annoying, so let’s get rid of it by making one last identification: we’ll identify lock sequences that differ only by leading zeros, and assume a canonical form that has no leading zeros. If the first inequality fails, we can force it to hold by adding leading zeros, thus increasing m. So now we’re left with
I like to imagine this condition as meaning, “Is there room in the attic for all the boxes?”. Maybe that will make more sense if I draw a picture:
This picture depicts the sequence (1,1,2,2,2,2,3,3) as an arrangement of 16 boxes, and an “attic” of area , all within an (n+1)×k rectangle. Now let’s flip it over and move the attic back to the top, like so:
We still have the same arrangement of boxes and the same size attic, just both flipped, so this new sequence – (2,6,8) in this example – is a valid sequence for the (k-1, n)-lock provided only the original was a valid sequence for the (n, k)-lock. Flipping the arrangement of boxes like this is known to mathematicians as conjugating a Young diagram. Notice how this process exchanges the values of m and dm.
So, we’ve shown that every lock sequence for the (n, k)-lock can be transformed into a lock sequence for the (k-1, n)-lock that has the same sum. It follows that it takes at least as many moves, in general, to open a (k-1, n)-lock as a (n, k)-lock. Since this works in both directions, we may conclude that m(n, k) = m(k-1, n).
I also posted this argument on Mathematics Stack Exchange.