Symmetry of bicycle-lock numbers

Question

Suppose you have a combination bicycle lock of this sort:

with $n$ dials and $k$ numbers on each dial. Let $m(n,k)$ denote 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.

For example $m(2,10)=6$ and $m(3,10)=10$.

I have found an efficient algorithm to compute these numbers, which reveals a symmetry I can’t currently explain:

$m(n, k+1) = m(k, n+1)$

This is such a striking symmetry that I guess it has a simple explanation. Can anyone find one?

Here’s the table of values for small $n$ and $k$, exhibiting the conjectured symmetry:

n\k|   2    3    4    5    6    7    8    9   10
---+---------------------------------------------
1  |   1    1    2    2    3    3    4    4    5
2  |   1    2    2    3    4    4    5    6    6
3  |   2    2    4    4    6    6    8    8   10
4  |   2    3    4    6    6    8    9   10   12
5  |   3    4    6    6    9    9   12   12   15
6  |   3    4    6    8    9   12   12   15   16
7  |   4    5    8    9   12   12   16   16   20
8  |   4    6    8   10   12   15   16   20   20
9  |   5    6   10   12   15   16   20   20   25
10 |   5    7   10   12   15   18   20   24   25

Answer 1

It has taken a few days, but I believe I can at last answer my own question. The strategy is to show that, for every combination of the $(n,k)$ lock, there is a combination of the $(k-1,n+1)$ lock that needs the same number of turns to unlock. The argument begins by grouping lock combinations into equivalence classes in such a way that equivalent combinations require the same number of turns to open.

---

Assume throughout that the destination combination, that opens the lock, is $n$ zeros.

The first trick is one I used before: 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 simplification: the order of the differences doesn’t matter. So we’ll say that two combinations are equivalent if they have the same multiset of differences, and we’ll write the differences as a nondecreasing sequence, to give a canonical form.

To motivate the next identification we’re going to make, let’s consider an example combination of the $(n=4, k=10)$-lock: 2593, which has differences 23447. The differences sum to $2k$, which means – as explained in my original blog post – that 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 particular they could have been $5$ and $6$ so that the differences were 23456. In this sense the combinations 2593 and 2594 are equivalent. We shall denote this equivalence class by the sequence (2,3,4), which we’ll call a lock sequence for the $(n, k)$-lock. Notice that the number of turns needed to open the lock is the sum of the terms of the lock sequence.

Now we’re going to characterise the lock sequences. Let $d_1, d_2, \dots, d_m$ be a nondecreasing sequence of natural numbers less than $k$ having length $m\leq n$; this is a lock sequence for the $(n,k)$-lock if these two inequalities hold:

$\sum_{i=1}^{m}d_i+(n+1-m)(k-1)\geq (n+1-m)k$

$\sum_{i=1}^{m}d_i + (n+1-m)d_m\leq(n+1-m)k$

They can be simplified to

$n+1-m\leq\sum_{i=1}^{m}d_i\leq(n+1-m)(k-d_m)$

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

$\sum_{i=1}^{m}d_i\leq(n+1-m)(k-d_m)$

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 lock sequence $(1,1,2,2,2,2,3,3)$ as an arrangement of 16 boxes, and an “attic” of area $(n+1-m)(k-d_m)$, all within an $(n+1)\times k$ rectangle.

Now let’s flip it over, like conjugating a Young diagram, and move the attic back to the top:

We still have the same arrangement of boxes – in particular the value of $\sum_{i=1}^{m}d_i$ remains the same – and the attic is the same size. So the conjugate sequence – $(2,6,8)$ in this example – is a valid sequence for the $(k-1, n+1)$-lock provided only the original was a valid sequence for the $(n, k)$-lock.

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+1)$-lock that has the same sum. It follows that it takes at least as many moves, in general, to open a $(k-1,n+1)$-lock as a $(n,k)$-lock. Since this works in both directions, we may conclude that $m(n,k) = m(k-1, n+1)$.

---

Another way of looking at it is to note that the above implies

$m(n,k) = \max\{\min\{ac,bd\}\ |\ a+b=n+1,c+d=k\mbox{ for }a,b,c,d\in\mathbb{N}\}$

which is symmetrical in $n+1$ and $k$. This expression also suggests another way to compute $m(n,k)$.

Answer 2

First let's consider a much simpler situation. If, instead of moving any group of adjacent dials, you can only move one dial, the maximum number of turns is trivial -- it's equal to $kn/2$. Note that this expression displays a sort of symmetry very similar to what you're seeing. To be jargony, the state space -- number of combinations -- has volume $kn$, which is a commutative expression, and we can only move through one square of state space at a time.

Now, if we look at the real problem, the state space is still of volume $kn$, but we can move through $k$ squares at a time, with some restrictions. It's easier to analyze if we can only move through one square, so we can look at the space of differences: 3879 becomes 592 and 23856 becomes 1571. In the space of differences we can only move two differences at a time - one up, one down, so 1571 might become 0572 -- but more importantly we have a volume $(k-1) \times n$ and we move a constant amount, so we expect to see a path length of $\Omega((k-1)n)$.

Now, the expression $m(n, k) = \Omega((k-1)n)$ exhibits the observed symmetry! It's just commutation -- if we take $m(k-1, n+1)$ we obviously have the same "volume" of "difference space". There's some intuition here but we still haven't derived the shortest path.

I'll borrow your expression $t = \sup_x(xk - xq - \min(r,x))$ for $xk = q(n+1) + r$ and note that the upper bound and lower bound are achieved precisely where $n+1 | xk$ and $n+1 | x(k-1)$, and that they are both proportional to $x(n+1-x)$, so have a shared maximum $x = (n+1)/2$. This gives us the diophantine equation $q(n+1) = xk$ and if we substitute $x \approx (n+1)/2$ we have $q \approx k/2$.

If these are both integers -- if $n$ is odd and $k$ is even -- we have $t(n, k) = m(n, k) = k(n+1)/4$. So that's a bit simpler already, and it follows the pattern which is nice.

However, the equation does not have a satisfactory solution if $k$ is odd or $n$ is even, so represents a sufficient but not necessary condition for a maximum. We might try to approximately solve the equation by choosing $x = (n+1)/2$, $q = k/2$, and finding a nearby lattice point. For $n = 200$, $k = 9$ we can choose $x = (n+1)/2 - (n+1)/2k = 101.5 - 11.1 = 89.9$ which is close to the true maximum $x = 89$ and suggestive of a more general pattern. I've spent an hour on this already though and should get back to work.

EDIT: I guess the takeaway is that the Diophantine equation $q(n+1) = xk$ is the same if we take $n \rightarrow k-1$, $k \rightarrow n+1$ to get $qk = x(n+1)$. Approximate solutions to this equation correspond to solutions of the general problem.