Puzzle 1: Michael can free his bike in four steps, as follows:
Start: 1/4/9/2
Turn #1 8 ahead: 8 8
Step 1: 9/2/9/2
Turn #2 2 ahead: 2 2 2
Step 2: 1/4/1/2
Turn #3 8 ahead: 8 8 8
Step 3: 1/2/9/0
Turn #4 4 ahead: 4 4
Step 4: 1/2/3/4
Puzzle 2: You can reach any combination from any start, and you can do it in four steps.
Let us start by noting how to set any particular digit of the combination.
Let's start with dial #2. Suppose that the current digit is A, and we need it to be B. Let X = B - A, which is what we have to increase A by. If this comes out negative, add 10. For puzzle #1, A was 4, and B was 2, so X = B - A = -2, so we add 10 to make X = 8.
To force the digit on dial 2 to become B and leave all other digits alone, do the following:
Advance dial #3 by X.
Advance dial #4 by 10-X.
For our example, this means
Start: 1/4/9/2
Turn #3 8 ahead: 8 8 8
Step 1: 1/2/7/0
Turn #4 2 ahead: 2 2
Step 2: 1/2/9/2
Notice that at the end, only dial #2 has changed, and it has changed to
the value we want.
The same trick works for dial #3, except that there, we
Advance dial #2 by X.
Advance dial #1 by 10-X.
For our example, this means
Start: 1/4/9/2
Turn #2 4 ahead: 4 4 4
Step 1: 5/8/3/0
Turn #1 6 ahead: 6 6
Step 2: 1/4/3/2
For dial #1, we have a little more work to do:
Advance dial #1 by X.
Advance dial #3 by 10 - X.
Advance dial #4 by X.
For our example, dial 1 is already 1. Let's pretend it's 8 instead,
so X is 3.
Start: 8/4/9/2
Turn #1 3 ahead: 3 3
Step 1: 1/7/9/2
Turn #3 7 ahead: 7 7 7
Step 2: 1/4/6/9
Turn #4 3 ahead: 3 3
Step 3: 1/4/9/2
So we were able to turn the first digit from 8 to 2 without altering
the others.
Dial #4 works similarly to dial #1:
Advance dial #1 by X.
Advance dial #2 by 10 - X.
Advance dial #4 by X.
For our example, A is 2 and B is 4, so X is 2.
Start: 1/4/9/2
Turn #1 2 ahead: 2 2
Step 1: 3/6/9/2
Turn #2 8 ahead: 8 8 8
Step 2: 1/4/7/2
Turn #4 2 ahead: 2 2
Step 3: 1/4/9/4
So we were able to turn the last digit from 2 to 4 without altering
the others.
Thus, one way to solve the puzzle is to follow the procedure to set each dial to its desired value, one at a time. This might take as many as 10 turns of the dial.
However, it's better to realize that we can simply sum up all the turns of each dial, and do each once. For our example, skipping dial #1 since it was already correct, we had to:
Dial#1 Dial#2 Dial#3 Dial#4
Fix dial 1 - - - -
Fix dial 2 - - 8 2
Fix dial 3 6 4 - -
Fix dial 4 2 8 - 2
-----------------------------------------------
8 12 8 4
and since 12 turns is the same as 2, we can set the combination
in four steps by turning the dial ahead 8, 2, 8 and 4 positions
respectively.
Since this procedure doesn't depend on the actual numbers of the final combination, it should be clear it works no matter what the starting and final combinations are.
If we let X1 be the value of X for dial 1, and so on, we can write a formula for the dial turns:
Dial#1 Dial#2 Dial#3 Dial#4
Fix dial 1 X1 - -X1 X1
Fix dial 2 - - X2 -X2
Fix dial 3 -X3 X3 - -
Fix dial 4 X4 -X4 - X4
-----------------------------------------------
X1-X3+X4 X3-X4 -X1+X2 X1-X2+X4
For our problem, X1 = 0, X2 = 8, X3 = 4, X4 = 2, so
our turns are ( 0 - 4 + 2, 4 - 2, - 0 + 8, 0 - 8 + 2 )
which is ( -2, 2, 8, -6 ) which simplifies (by adding 10 to
negative values) to (8,2,8,4).
To a mathematician, this is all similar to a change of basis problem. In particular, we have seen that any combination can be created by our legal moves, which we will call T12, T123, T234 and T24, where T12 means turn dials 1 and 2 the same amount, and so on.
Given a desired combination, we'd really like to be able to use moves T1, T2, T3 and T4, where T1 means we can move dial 1 a certain number of positions, without affecting the other dial settings.
It's obvious that the complicated moves can be represented by combinations of the simple moves:
T12 = T1 + T2
T123 = T1 + T2 + T3
T234 = T2 + T3 + T4
T34 = T3 + T4
so if we know how to do T1, T2, T3 and T4, it's easy to
simulate T12, T123, T234 and T34.
The hard part, which we just did, was to go the other way, and discover:
T1 = T12 - T234 + T34
T2 = T234 - T34
T3 = -T12 + T123
T4 = T12 - T123 + T34
where a symbol like "-T12" means either go in the reverse direction,
or else go ahead 10 minus the amount moved by the positive dials.
And this just means that the matrices
1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1
and
1 0 -1 1
0 0 1 -1
-1 1 0 0
1 -1 0 1
are inverses.
Back to The Lock Puzzle;