# Bike lock puzzle

I was wondering this when using my bike lock, a combination lock with four dials, each of which has ten digits (0-9) on it in numerical order.

Suppose a bicyclist decides that, from now on, after putting in his combination on this lock, he will only give the lock one twist to close it. So, he chooses between 1 and 4 adjacent dials, and rotates them any number of spaces (other than a multiple of 10, to avoid having the lock end this procedure in a closed position!)

Unbeknown to the bicyclist, a thief is following him. The thief knows that the bicyclist uses this procedure to secure his bike. Over a period of days, the thief notes each combination the lock ends up on. What's the fewest observations that the thief needs to make before she can deduce the combination with certainty? What's the fewest observations that she needs to make before she can reduce it to 10 possibilities? How can a shrewd (but stubborn) bicyclist maximize the number of observations necessary without repeating a combination?

This seems simple enough that I'm sure it's been solved before, but I don't know where to start on it.

• Code breaking, or error correction on a noisy channel. Unless the lock has only 4 cylinders (the code has only four digits), it should be easy after three or four trials to obtain most of the code. The worst case will be if the cyclist locks it the same way, or in one of two or three ways, every time. Gerhard "Ask Me About System Design" Paseman, 2012.08.02 – Gerhard Paseman Aug 2 '12 at 21:09
• If the cyclist always leaves the lock showing 0000, the thief can only ever narrow down the set of possibilities to (4+3+2+1)*9 = 90 combinations. (4 choices of dial to rotate, 3 choices of pairs of adjacent dials, etc., and 9 possible non-identity rotations.) So the answer to your first two questions is $\infty$. – Trevor Wilson Aug 2 '12 at 21:32
• The first two questions ask for the fewest possible pieces of information needed, so the cyclist's restriction is unnecessary for those questions. – user25491 Aug 2 '12 at 21:45
• Glad to know I'm not the only one who gives serious thought to the trade-off between security and laziness in scrambling my bike lock. In fact, I have arrived at a similar conclusion as others here have: if I always scramble to the same position, I get more security for same laziness than if I scramble same number of positions randomly. – Yoav Kallus Aug 2 '12 at 22:54
• @Ng Yong Hao: I'm just pointing out that nothing in the first two questions says that the bicyclist cannot repeat a combination, so the same combination might be observed multiple times. "The lock shows 0000 on Monday" and "the lock shows 0000 on Tuesday" are different observations. – Trevor Wilson Aug 3 '12 at 17:53

If you are clever, the thief needs 49 different settings of the dials to know the correct setting with certainty. This is more than half of all $90 = 4\cdot9 + 3\cdot9 + 2\cdot9 + 1\cdot9$ possible settings you can produce (when moving one dial, two adjacent dials, three adjacent dials, and all four dials, respectively, into their nine possible incorrect positions).

Let the dials be $(a, b, c, d)$. Let the correct position be $(0, 0, 0, 0)$ to have a mental picture. If you put $a$ in eight different positions, say 1, 2, ..., 8, then the thief does not yet know with certainty the correct one - although she knows the correct positions $0$ of the other three. So if you decided to turn one or more other dials leaving $a$ at $0$, she would quickly know the complete correct setting. But if you put $(a, b)$, $(a,b,c)$, and $(a,b,c,d)$ also in the eight different positions avoiding $a = 9$, you have $4\cdot8 = 32$ positions without revealing the correct information.

You can do even better, if you choose to start with $b$. Then you can extend your number of settings by moving $(a,b)$, $(b,c)$, $(a,b,c)$, $(b,c,d)$, and $(a,b,c,d)$ supplying $(1 + 2 + 2 + 1)\cdot8 = 48$ settings in total. (Of course the order you choose does not matter.)

You would get the same opportunity with $c$ instead of $b$. $d$ however, like $a$, would supply only 32 possible positions.

The maximum number of different positions, before the thief has discoverd the correct one, is for $n > 2$ digits and an even number $m$ of dials:

$$(n-2)\cdot\frac{m}{2}\cdot\frac{m+2}{2}.$$

For an odd number $m$ of dials you get

$$(n-2)\cdot(\frac{m+1}{2})^2.$$

If no single dial is moved, we have only 48 settings: 3 pairs, 2 triples and 1 quadruple in 8 positions each. But if pair $(a,b)$ has been moved twice, pair $(c,d)$ cannot be moved without revealing the secret. Hence, we get only 40 settings. That is less than the constructed 48. So, in order to maximize the number of the secret-maintaining settings, we have to move also at least one single dial. But having moved it twice, we can no longer move any other single dial or the pair not containing the first. This subtracts 36 from the 90 possible settings. Since of the remaining 54 settings 6 are always "the nineth", i.e., revealing the secret, we have at most 48 settings.
• @S. Carnahan: Thank you. A direct proof? Not quite sure. I only assume that when anywhere in the sequence of 48 settings $b$ will remain 0 for two times, then $b = 0$ will be known, whereas $(0,b,0,0)$ is already known after twi single moves of $b$. – user34804 Jun 24 '13 at 14:02