Combinatorics and Probability Riddles

[Snarky]

Aha, I got one! This is what you might call a problem from real life (which means I don't know the answer off the top of my head)...

I have a 4-wheel combination lock for my bike. Each wheel has 10 different possible positions (0-9):



Let's say my code is 1234. When I lock it, I spin each wheel into a random position. I want to be able to unlock it with as little effort as possible. To simplify a bit, let's say that "effort" is measured in how much I have to turn each wheel. (So if I have to turn the first wheel 3 positions, the second 4, the third 1 and the fourth 2, the total effort is 3+4+1+2=10.)

Obviously, if I just set the wheels one-by-one, the worst-case scenario is that I have to turn each wheel 5 positions, so the total effort is 4*5=20. On average it will be half that, 10 (2.5 per wheel). However, if I grip the wheels a little differently, I can actually just as easily turn two (adjacent) wheels at a time. (Three is possible but more trouble than it's worth, so let's ignore that.) This changes things significantly, because if I, like in the above example, see that I have to turn the first wheel three positions and the second 4 (in the same direction), I can turn them 3 positions together, and then I just have to turn the second wheel 1 position.

So here's the challenge:

1. What is the worst-case and the average effort now (for the most efficient way to solve the lock from any random start position)?
2. Can you come up with an algorithm to work out the optimal way to solve the lock (which moves to do in which order) from any start position?

[Snarky]

All right, I'll have a go at at least part of the problem, then. For simplicity and without loss of generality, let's now say that the code is 0000. So the number of turns (degree of rotation) needed to put it a wheel in the right position from each starting position are:

0:0
1:1
2:2
3:3
4:4
5:5
6:4
7:3
8:2
9:1

(Notice that we have symmetry around 5: 6 and 4 are equivalent, as are 7 and 3, 8 and 2, and 9 and 1.)

Let's start by putting some upper and lower bounds on the worst-case scenario.

Clearly, the amount of work can't be greater than if you're turning the wheels individually, so an upper bound on the maximum effort needed is 20. To establish a lower bound, we can divide up the problem into steps, and first just look at what it would take to get the two wheels on the ends (X--X) in position. Since there's no interference between them, it doesn't matter if we turn them by themselves or together with one of the other wheels, in the worst case it's still 5 per wheel, 10 total. That gives us a lower bound.

We can now proceed to tighten these bounds. Let's add one of the wheels in the middle into consideration (XX-X). Now the wheel to the right is still independent (there's no way to have its turning affect or by affected by the other wheels we're considering), so we can just look at positioning the two wheels on the left together. The approach we'll consider is to start by turning the first wheel into position, either by itself or with the other one depending on whether it will improve the starting position of the second wheel, and then turn the second wheel into position. Because of symmetry and because rotation is commutative, this is equivalent to any other approach.

The cost of positioning the first wheel is still 0-5. The cost of the final turn to adjust the second wheel, though, depends on how much we turned the first wheel (and therefore optionally the second along with it). So, for example if the second wheel started out at 5, any turn at all would reduce the remaining turns needed by that same amount (turn it 4 and there's only 1 left, turn it 3 and there are 2 left, etc.), so the max cost is 5 - cost_of_first wheel, and the total cost of them both is always 5.

So if we think about how many turns we can make at most (up to 5) that leaves us in a worse (or equivalent) starting position, for each of the starting positions of the second wheel, we get:

0:5 (-> 5)
1:5 (-> 6)
2:5 (-> 7)
3:4 (-> 7)
4:2 (-> 6)
5:0 (-> 5)
6:2 (-> 4)
7:4 (-> 3)
8:5 (-> 3)
9:5 (-> 4)

So the max cost of both wheels together is 7 (5+2 or 4+3). So the max cost of setting three wheels (XX-X) is 7+5=12, which is also a lower bound on the cost of setting all four. Now we can use a similar argument with the two wheels on the right, to show that an upper bound on the max cost of all four wheels is 14.

Hmmm... I think I'll leave it there for now. The worst-case cost is somewhere between 12 and 14, but establishing the precise figure gets a bit more complicated, because we have to consider possible interactions between the wheels in the middle as well.

[SinSin]

2 words

Bolt cutters

100% success rate