Decoding the mysterious symmetry of the bicycle lock numbers

2014-02-25 § Leave a comment

Suppose you have a lock of this sort bicycle lock that has n dials and k numbers on each dial. Let m(nk) 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(nk).

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

It looks as though m(ab+1) = m(ba+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 (ab+1) and a (ba+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:

  1. Equivalent combinations need the same number of turns to unlock.
  2. there is a natural bijection between the equivalence classes of combinations of the (ab+1)-lock and the equivalence classes of combinations of the (ba+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 (nk)-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 2593 and 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 d1d2, …, dm be a nondecreasing sequence of natural numbers less than k having length m ≤ n; this is a lock sequence for the (nk)-lock if

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

which simplifies 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?

Can we fit the boxes into the attic?


This picture depicts the 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)×k rectangle. Now let’s flip it over and move the attic back to the top, like so:
Flipped

Flipped

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 (nk)-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 (nk)-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 (nk)-lock. Since this works in both directions, we may conclude that m(nk) = m(k-1, n).

I also posted this argument on Mathematics Stack Exchange.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Decoding the mysterious symmetry of the bicycle lock numbers at Bosker Blog.

meta

Follow

Get every new post delivered to your Inbox.

Join 775 other followers

%d bloggers like this: