8
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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 $\endgroup$ Aug 2 '12 at 21:09
  • 4
    $\begingroup$ 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$. $\endgroup$ Aug 2 '12 at 21:32
  • 1
    $\begingroup$ The first two questions ask for the fewest possible pieces of information needed, so the cyclist's restriction is unnecessary for those questions. $\endgroup$
    – user25491
    Aug 2 '12 at 21:45
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 2 '12 at 22:54
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 3 '12 at 17:53
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is very nice (and much better than what I wrote), but do you have a proof of maximality? $\endgroup$
    – S. Carnahan
    Jun 24 '13 at 13:51
  • $\begingroup$ @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$. $\endgroup$
    – user34804
    Jun 24 '13 at 14:02
  • 1
    $\begingroup$ @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. $\endgroup$
    – user34804
    Jun 24 '13 at 18:51
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Let me be a contrarian and attempt to refute @user34804's answer $48$ to question three (how many days max without thief knowing the correct combination, with different configurations each day). This answer seems to have stood for seven years, so probably I'm making some silly mistake or we are interpreting the question differently.

Let $G$ be a graph. Its locking number is the maximal $n$ such that for some distinct $u, v \in V$ we have $|N_1(u) \cap N_1(v)| = n$, where $N_1(w) = \{w' \in V(G) \setminus \{w\} \;|\; \{w, w'\} \in E(G)\}$ is the open neighborhood of $w$ of radius $1$. The motivation for this terminology is that if the nodes of $G$ represent the different states of a bike lock, and the edges represent moves that the bicyclist may make after locking their bike, then this $n$ is the maximal number of days that may pass before the thief knows the combination: If $N_1(u) \cap N_1(v) = n$ then we can list elements of $N_1(u) \cap N_1(v)$ for $n$ days, and the thief still does not know whether $u$ or $v$ is the right combination. If we list any $n+1$ elements of some $N_1(u)$, then by the choice of $n$ this $u$ is uniquely determined, as no other node $v$ has those $n+1$ elements in its open neighborhood.

In the question, the graph has nodes $\mathbb{Z}_{10}^4$ and edges are $\{u, u+v\}$ where $$ v \in \{aa00, 0aa0, 00aa, aaa0, 0aaa, aaaa \;|\; a \in \mathbb{Z}_{10} \setminus \{0\}\}. $$ There's a lot of symmetry, so it is possible (though tedious), to verify that the maximal intersection satisfies $|N_1(u) \cap N_1(v)| = 14$, attained for example by the pair $u = 0000, v = 9000$, for which the intersection is $$ \{1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 0100, 0110, 0111, 9900, 9990, 9999 \}. $$

So the locking number for this graph is $14$, and thus it is on day $15$ that the thief can finally be sure to open the lock with just one move. (This thief seems to be even lazier than the bicyclist.)

I don't really understand @user34804's deduction, but one claim they seem to make (switching to their notation) is that if you move $a$, $(a,b)$, $(a,b,c)$ and $(a,b,c,d)$ respectively by $1$ through $8$ clicks, and the correct combination $(0,0,0,0)$, then the thief still doesn't know whether the first dial should have $0$ or $9$. But obviously they can, namely the thief knows that the correct combination is either $(0,0,0,0)$ or $(9,0,0,0)$ after the moves of the first dial. Given this information, many further moves of $(a,b)$, $(a,b,c)$ and $(a,b,c,d)$ reveal that it is $(0,0,0,0)$, for example if we rotate $(a,b)$ by $1$, we get $(1,1,0,0)$ from $(0,0,0,0)$ and there is no way to reach it from $(9,0,0,0)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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