Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
    
indeed, not sure what I was thinking about... –  user88595 Feb 20 at 18:46
    
Do you have an example of a starting position with $n=4$ and $k=8$ or $10$ that requires the value listed in the table above? –  John Habert Feb 20 at 19:35
    
@JohnHabert Sure, for n=4 and k=10, and assuming the combination 0000 opens the lock, the combinations 4826 and 6284 require 12 moves. –  Robin Houston Feb 20 at 19:49
    
This is probably obvious, but from your table we also have $m(n, n+1) = m(n, n)$ and $m(2k, 2k) = k^2$ while $m(2k+1, 2k+1) = k(k+1)$ - or, to combine these into a single expression, $m(n,n) = \lfloor\frac{n}{2}\rfloor\cdot\lfloor\frac{(n+1)}{2}\rfloor$. It's very possible there's a similar closed-form expression for $m(n,k)$ that explains the symmetry. –  Steven Stadnicki Feb 21 at 16:37
    
In fact, several of the small-$k$ values have closed forms too: $m(n,2) = \lfloor\frac{(n+1)}{2}\rfloor$, $m(n,4) = 2m(n,2)$, $m(n,3) = \lfloor\frac{(2n+2)}{3}\rfloor$, etc. I think a little more chewing may give a fully closed form... –  Steven Stadnicki Feb 21 at 16:46

2 Answers 2

up vote 7 down vote accepted

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: Can we fit the boxes into the attic?

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:

Flipped

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)$.

share|improve this answer
    
Congratulations! Yes, I think that's compelling. I'd got as far as your "box" picture but not to the necessary & sufficient inequality. Is it worth emphasising that "the same arrangement of boxes" in the conjugate diagram means the same count of boxes, i.e. that the term $\Sigma d_i$ remains the same after conjugation? –  HTFB Feb 25 at 7:49

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.

share|improve this answer
    
What is the function $\Omega$ here? –  HTFB Feb 24 at 12:05
    
Ω is part of big O notation. See Wikipedia. I actually should have used big-theta (asymptotically related by a constant), as that's what I meant. –  mason bogue Feb 25 at 3:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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