6
$\begingroup$

The image shows numbers on ring-dials on a curiously-geared combination lock, where the current setting is (3,3,3,3) and ring sizes are (5,7,8,11), inner to outer. The setting (0,0,0,0) opens the lock.

When you rotate any ring, rings outside it move twice as fast in the same direction, while rings inside it move twice as fast in the opposite direction. For example, moving the 7-ring in the diagram 1 unit to 2 changes the 8- and 11-rings to 1 and the 5-ring to 0, for a new state of (0, 2, 1, 1).

Can you find a minimal sequence to open this lock?

(The cost of a sequence is the total number of places that selected dials are turned in one direction. There is no cost for selecting a dial and direction. For example, if you turn the 5-ring 18 places CCW and 11 places CW, and then the 11-ring 29 places CCW, the cost is 18+11+29 = 58. At most one dial can be selected at a time.)

CGCL S=(5,7,8,11), B=(3,3,3,3)

$\endgroup$
11
$\begingroup$

First, what do we know about this puzzle?

  • There are 5*7*8*11 = 3080 possible positions.
  • Moves do not affect each other, so if you have a good set of moves, you can do them in any order.
  • There must be at least one move of the 8 ring, but not necessarily any of the others.

Given this, it is a relatively simple algorithm to find the shortest sequence of moves.

What I did was to start with a list containing only (0,0,0,0), then for each item in that list, I did a +5,-5,+7,-7,+8,-8,+11,-11. For each item produced by this, I check if it is in the list and if not, add it to the end.

I had it stop when it got to (3,3,3,3).

(0,0,0,0) -> +5
(1,2,2,2) -> +7
(4,3,4,4) -> -8
(1,5,3,2) -> -8
(3,0,2,0) -> -8
(0,2,1,9) -> -8
(2,4,0,7) -> -8
(4,6,7,5) -> -11
(1,1,1,4) -> -11
(3,3,3,3)

So the minimum number of moves is 9. One example is(just reversing my list):
+11,+11,+8,+8,+8,+8,+8,-7,-5

Update:
The maximum distance from any position to any other position is 14. Here is a list of the distances and the number of points for each distance. This is done from (0,0,0,0), but it holds for any point.

0: 1
1: 8
2: 32
3: 84
4: 168
5: 284
6: 420
7: 397
8: 344
9: 330
10: 324
11: 324
12: 250
13: 100
14: 14

An example of an item that is 14 moves from (0,0,0,0) is (3,1,5,1), which happens to be the last item in my sequence.

The closest items with 3 0's are (0,0,0,3) and (0,0,0,8), which are 5 moves away.
The closest items with 3 0's and a 1 are (1,0,0,0) and (0,0,1,0), which are 7 moves away.
The furthest item with 3 0's and a 1 is (0,1,0,0) which is 12 moves away.
(0,0,0,1) is 8 moves away (to complete the set).

Update 2:
The question was asked how I knew the 8 ring must move at least once, but not necessarily any of the others. There are two different parts to this.

First, if you never move the 8 ring, moving other rings always causes it to move 2, which means it can only ever be at 1, 3, 5 or 7. So you must move it at least once to get it to an even number.

Second, to never move another ring: I expected this to be true because all the ring sizes are relatively prime to each other (and to the moves, except for the 2-move and 8-ring), so if I move the 8 ring 3080 times, I should go through every permutation. If I move any other ring 1540 times, I'll go through half the permutations (because in that case, the 8 ring only stays on odd numbers). To verify this, I put together a quick spreadsheet to simulate moving each ring +1 3080 times. The spreadsheet showed this to be correct. It also showed that you can get to (0,0,0,0) by moving the 8 ring -1 only 51 times.

$\endgroup$
  • 1
    $\begingroup$ Could you explain how you determined "There must be at least one move of the 8 ring, but not necessarily any of the others."? $\endgroup$ – Vicky Aug 13 '14 at 9:42
  • $\begingroup$ If you move the 8-ring 51 times you reach (3,3,3,3). $\endgroup$ – Florian F Sep 14 '14 at 17:47

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.