The bicycle lock problem
2014-02-18 § 3 Comments
Don’t lock your bicycle with a combination lock. Someone will steal it: I learnt this the hard way. It’s quite easy to open a combination lock by feel, without knowing the combination. Try it: with a bit of practice, you can open the lock with your eyes shut. (It’s easier to do this with an old wobbly lock than a tight-fitting new one.)
But suppose, for the sake of mathematics, that you have ignored this good advice. How many turns of the lock do you need to make to unlock your bike? You will notice that you can turn a number of adjacent dials together in the same direction, almost as easily as turning a single dial – so we’ll say turning any number of adjacent rings one place counts as a single turn.
Of course the answer depends on many factors: how many rings the lock has, how many numbers are on each ring, what the correct combination is, and the current state of the lock: which numbers are uppermost to begin with. Let’s say the lock has n rings, and each ring has the k numbers 0, …, k-1. (Real bicycle locks often have n=4 and k=10. The one depicted above has n=5.) Let’s also suppose that the correct combination is all 0s.
If you were only allowed to turn one dial at a time, this would be very easy. A dial showing digit d would require min{d, k–d} turns, and we could just add up the number of turns required for each dial. But we can turn several adjacent dials at once, which makes it more interesting. For example, if n=2 and k=10, the combination 55
can be unlocked in 5 turns rather than 10, and the combination 46
can be unlocked in 6 turns rather than 8.
Our goal here is to find an efficient algorithm to compute the maximum number of turns you might need to unlock your bike, given n and k, but we’ll discover some interesting things along the way. We’ll begin by working out how many turns are needed starting from a specific combination.
To see how many turns are needed, it is helpful to look at the differences between adjacent numbers. Suppose we have the combination 4831
with n=4 and k=10: compute the differences modulo k, as follows:
with the subtraction shown in blue and the result of this subtraction modulo k shown in red.
It’s useful to look at the differences rather than the actual numbers on the dials, because the effect of turning multiple adjacent dials together is simpler: a turn corresponds to adding 1 to one of the differences while subtracting 1 from another. For example, if we turn the middle two dials so that the lock reads 4941
, the differences are then 45579
. Conversely, if you add 1 to one of the differences while subtracting 1 from another, this corresponds to turning the dials that lie between these two differences. If a, b are differences, we’ll write (a+, b-) for the move that adds 1 to a and subtracts 1 from b.
Now let’s look at the maximum number of turns you could need for particular n and k, which we’ll call t_{n,k}, or t for short. As an example, for n=2 and k=10 you can always unlock your bike in 6 turns, and sometimes 6 are necessary – e.g. starting from 48
– so we say t_{2,10} = 6.
Consider the effect on the differences of a minimal unlocking sequence: one that’s as short as possible. The key observation is that, in a minimal unlocking, each difference is changed in one direction – up or down – but never both. If the same difference is changed both up and down, the unlocking sequence could have been shortened by not doing that, so it isn’t minimal. To be precise, suppose a, b and c are three differences and that the unlocking sequence contains the moves (a+, b-) and (b+, c-). Then we can replace these two moves with the single move (a+, c-); or if a and c happen to be the same then we remove both moves. Either way we have shortened the unlocking sequence, which means it wasn’t minimal. Another important observation about minimal unlocking sequences is that every difference is changed by fewer than k steps: so it never wraps round back to where it started. Again there is a similar argument to before, showing that any unlocking sequence where a difference makes a complete revolution cannot be minimal. Bear in mind, too, that the unlocking is finished when all the differences are 0.
Now the question is, how many of the differences go up and how many down. For this we add up all the differences. This sum is 0 modulo k, so must be equal to xk for some natural number x. Now we shall see that x of the differences go up, and the rest down. This is not obvious, I don’t think, but isn’t hard to see if you think about it in the right way. Consider how the sum of differences changes as the unlocking sequence is performed. This sum is always 0 modulo k, and goes from xk at the start to 0 at the end. Therefore it must, at a minimum, be reduced x times. Now, a move that reduces the sum is one that increments one of the differences from k-1 to 0 whilst reducing the value of another. In a minimal sequence, this will the the last move for the difference that was incremented and that difference must have been one of the ones that went up. Conversely the final move for any difference that goes up must be to roll it over from k-1 to 0. So indeed precisely x of the differences go up in a minimal unlocking sequence.
We can compute the number of turns as the sum of the differences that go down, and for a minimal unlocking sequence these should be the smallest ones. So the number of turns needed is the sum of the smallest (n+1-x) differences. Now let’s turn it round, and look at the maximum number of turns needed for a particular x. We’ll write this as t_{n,k}(x), or t(x) for short. Since we’ve fixed x, we know that the sum of the differences is xk. If the differences could be fractions, rather than having to be whole numbers, the worst-case scenario – maximising the number of turns needed – would be for them to be distributed evenly so that each difference is and the sum of the (n+1-x) smallest is therefore .
This gives us an upper bound on t_{n,k}(x), but we need to work a little harder to get the exact value. Let q_{x} and r_{x} be the quotient and remainder of xk/(n+1), so in other words xk = q_{x}(n+1) + r_{x}, where 0 ≤ r_{x} < n+1. Distributing the differences as evenly as possible means we have (n+1-r_{x}) that are q_{x}, and the remaining r are q_{x}+1. The smallest x of these consists of min{x, n+1-r_{x}} q_{x}’s and max{0, r_{x}-x} (q_{x}+1)’s, so t_{n,k}(x) – the sum of the smallest x – is (n+1-x)q_{x} + max{0, r_{x}-x}. Rearranging gives the alternative form,
We already found the upper bound
and in a similar way there is a lower bound
Here is a graph showing how q_{x}, r_{x} and t_{n,k}(x) vary with x, for n=200 and k=9. It also shows the upper and lower bounds from inequalities (2) and (3).
You can see how the true value of t zig-zags between the upper and lower bounds, and attains its maximal value 445 at x=89 and x=112. You may also be surprised to see that t behaves symmetrically: this isn’t quite obvious from the formula, though it’s easy enough to prove once you know to look for it.
It remains only to compute the actual maximum value of t over all x. It seems that some amount of brute-force searching over values of x is needed here, or at least I don’t know a better way that always works. But we can limit the search quite substantially, using two observations. First, within a particular q-block – a block of x values that have the same q_{x} – the maximal value within that block is attained at one of the endpoints. And second, the maximum value must lie between , because these are the x values where a horizontal line tangent to the lower bound curve intersects the upper bound curve:
Using the symmetry of t, if we search in this whole range then it is sufficient to consider one of the endpoints of the q-block, say the left-hand one.
Putting these together, we obtain the following algorithm, here implemented in Python 2:
from __future__ import division from math import floor, ceil, sqrt def max_t(n, k): m = 0 root_k = sqrt(k) q = int(ceil((k - root_k) / 2)) range_end = q + int(floor(root_k)) while q < range_end: x = int(ceil(q * (n+1) / k)) q, r = divmod(x*k, n+1) t_x = x * (k - q) - min(x, r) if t_x > m: m = t_x q += 1 return m
It’s reassuring to learn that, if you had a bike lock with 371 dials and 97 numbers on each dial, you could always open it in 9016 turns – though perhaps disappointing to learn that you will sometimes need as many as that.
Here’s a table of the results for n, k up to 20.
_{n}\^{k} | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 7 | 7 | 8 | 8 | 9 | 9 | 10 |
2 | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 8 | 8 | 9 | 10 | 10 | 11 | 12 | 12 | 13 |
3 | 0 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 | 10 | 10 | 12 | 12 | 14 | 14 | 16 | 16 | 18 | 18 | 20 |
4 | 0 | 2 | 3 | 4 | 6 | 6 | 8 | 9 | 10 | 12 | 12 | 14 | 15 | 16 | 18 | 18 | 20 | 21 | 22 | 24 |
5 | 0 | 3 | 4 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 18 | 18 | 21 | 21 | 24 | 24 | 27 | 27 | 30 |
6 | 0 | 3 | 4 | 6 | 8 | 9 | 12 | 12 | 15 | 16 | 18 | 20 | 21 | 24 | 24 | 27 | 28 | 30 | 32 | 33 |
7 | 0 | 4 | 5 | 8 | 9 | 12 | 12 | 16 | 16 | 20 | 20 | 24 | 24 | 28 | 28 | 32 | 32 | 36 | 36 | 40 |
8 | 0 | 4 | 6 | 8 | 10 | 12 | 15 | 16 | 20 | 20 | 24 | 25 | 28 | 30 | 32 | 35 | 36 | 40 | 40 | 44 |
9 | 0 | 5 | 6 | 10 | 12 | 15 | 16 | 20 | 20 | 25 | 25 | 30 | 30 | 35 | 36 | 40 | 40 | 45 | 45 | 50 |
10 | 0 | 5 | 7 | 10 | 12 | 15 | 18 | 20 | 24 | 25 | 30 | 30 | 35 | 36 | 40 | 42 | 45 | 48 | 50 | 54 |
11 | 0 | 6 | 8 | 12 | 14 | 18 | 20 | 24 | 25 | 30 | 30 | 36 | 36 | 42 | 42 | 48 | 49 | 54 | 55 | 60 |
12 | 0 | 6 | 8 | 12 | 15 | 18 | 21 | 24 | 28 | 30 | 35 | 36 | 42 | 42 | 48 | 49 | 54 | 56 | 60 | 63 |
13 | 0 | 7 | 9 | 14 | 16 | 21 | 24 | 28 | 30 | 35 | 36 | 42 | 42 | 49 | 49 | 56 | 56 | 63 | 64 | 70 |
14 | 0 | 7 | 10 | 14 | 18 | 21 | 24 | 28 | 32 | 36 | 40 | 42 | 48 | 49 | 56 | 56 | 63 | 64 | 70 | 72 |
15 | 0 | 8 | 10 | 16 | 18 | 24 | 27 | 32 | 35 | 40 | 42 | 48 | 49 | 56 | 56 | 64 | 64 | 72 | 72 | 80 |
16 | 0 | 8 | 11 | 16 | 20 | 24 | 28 | 32 | 36 | 40 | 45 | 49 | 54 | 56 | 63 | 64 | 72 | 72 | 80 | 81 |
17 | 0 | 9 | 12 | 18 | 21 | 27 | 30 | 36 | 40 | 45 | 48 | 54 | 56 | 63 | 64 | 72 | 72 | 81 | 81 | 90 |
18 | 0 | 9 | 12 | 18 | 22 | 27 | 32 | 36 | 40 | 45 | 50 | 55 | 60 | 64 | 70 | 72 | 80 | 81 | 90 | 90 |
19 | 0 | 10 | 13 | 20 | 24 | 30 | 33 | 40 | 44 | 50 | 54 | 60 | 63 | 70 | 72 | 80 | 81 | 90 | 90 | 100 |
20 | 0 | 10 | 14 | 20 | 24 | 30 | 36 | 40 | 45 | 50 | 55 | 60 | 66 | 72 | 77 | 81 | 88 | 90 | 99 | 100 |
Can anyone find a simpler algorithm?
Open questions
This table raises as many questions as it answers. Let’s write the (n,k) entry as m(n,k); then the following conjectures are consistent with the numerical evidence.
- m(n, k) = m(k-1, n+1)
- m(n, n+1) = m(n, n+2) = m(n-1, n+3) =
- m(n-1, kn) = k m(n-1, n) =
Update: I now have an explanation for the symmetry m(n, k) = m(k-1, n+1).
That analysis also explains the other observations above, since it shows that
m(n, k) = max{ min{ac,bd} | a+b=n+1, c+d=k, a,b,c,d∈ℕ }
In particular, if there are a,b,c,d such that a+b=n+1, c+d=k and ac = bd then m(n, k) = ac = bd. This is the case for the second and third bulleted observations.
Thanks
Thanks to radil for posing this problem, and to _Navi_ for some interesting remarks.
In paragraph 10, surely “Therefore it must, at a minimum, be reduced _*x*_ times”?
Corrected, thanks!
[…] the previous post, we found an algorithm for computing these bicycle lock numbers, revealing a mysterious symmetry, […]