Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
4  
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
1  
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
2  
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
1  
@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

2 Answers 2

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

Addition: Maximality

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.

share|improve this answer
    
This is very nice (and much better than what I wrote), but do you have a proof of maximality? –  S. Carnahan Jun 24 '13 at 13:51
    
@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
    
@S. Carnahan: Yes, after some pondering, I think I have the proof of maximality. After all 8 single moves of b (same holds when using c) have been done, b = 9 will solve the puzzle. b = 0 in connection with moving different dials will also solve the puzzle, because (0,b,0,0) is already known after few single moves of b. And if all 8 single moves have not yet been done, then we are below 48 moves. –  user34804 Jun 24 '13 at 18:51

Here's an incomplete analysis to get things started. Lets assume the bicyclist is constrained to use a different combination each day, to prevent degenerate strategies - this only allows for 90 days, but the bicycle will be stolen long before then.

In order for the thief to work out the precise number in two observations, I think it is necessary and sufficient that the bicyclist move two unequal, non-complementary subsets of dials by different amounts. In order to keep this from happening, the bicyclist has three basic strategies: use the same subset every time, use complementary subsets, and shift the dials by the same amount every day.

A strategy of using complementary subsets will create a problem on the third day - one of the sets will have a shift by differing amounts. A strategy of shifting the dials by the same amount but changing the subsets will yield a problem on the fourth day or so - I haven't worked out the cases. By shifting the same dial by differing amounts, the bicyclist can keep the bicycle from the thief until the ninth day.

share|improve this answer

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.