Lucky 7
The purpose of the game, as with Loyd's Fifteen and Sliders, is to return the counters into their Home position, position they were in before reshuffling. The puzzle consists of several counters placed on two intersecting circles. There are six points of control: the two central counters and the two pairs of counters adjacent to the central ones. In the case of 7 counters, besides the empty counter, these are numbered 1, 7, 3, 4, 5. Clicking on the upper counters induces clockwise rotations. Clicking on the lower counters results in counterclockwise rotations. Left counters rotate the left circle. Right counters rotate the right circle. The middle ones handle the whole set. The empty counter is skipped in all cases.
With 7 counters the puzzle is solvable for any starting configuration. You can experiment with this by hitting the Cheat button which swaps the second and the first counters.
If the "Cycles" box is checked, a permutation of counters needed to solve the puzzle is displayed. The permutation is presented as a product of cycles.
| What if applet does not run? |
Theorem
With the number of counters equal to 7 the puzzle is solvable for any starting configuration.
Proof
Let a denote one clockwise shift of the left circle. Let b stand for a counterclockwise shift of the right circle. Then executing the following sequence of moves
swaps the counters 6 and 7 and also the pair 2 and 4. In other words, this sequence of moves leads to the permutation
On the other hand, for the sequence m = aabaabaabaabaab, we have
Let the global clockwise rotation be denoted as c. Then
We thus found a sequence of moves that swaps two adjacent counters 6 and 7. This shows that any two adjacent counter can be swapped by a suitable sequence of moves without disturbing other counters. Indeed, depending on k, the sequence ckncmc-1c-k swaps any pair of adjacent counters. For example, if k = 1, then counters 1 and 7 are swapped. If k = 2, the counters 1 and 2 are swapped, and so on.
Assume now we wish to swap another pair of counters, say, a and b. Let f be a sequence of moves that brings a into position 6 while it brings b into position 7. We are not concerned with what happens to the rest of counters. Swap the counters in the positions 6 and 7 and then apply inverses of moves from f but in the reverse order. All counters will return to their original position but a and b that will swap their positions.
Thus all transpositions can be generated by our basic cycles. This proves the theorem because then counter 1 can be swapped into its rightful position, then counter 2, and so on. Q.E.D.
Remark 1
The sequences m and n may appear to be produced out of hat. They were. I have no other explanation, except for saying that I just toyed with the puzzle for a while trying simple sequences of moves and watching permutation thus obtained. I am pretty sure that the same result can be obtained with shorter sequences.
Remark 2
I am grateful to Don Greenwell for detecting an error in the original proof. He also pointed out that the idea of the last paragraph of the proof, where we moved two counters a and b into swappable positions, does not require those positions be adjacent. The proof thus shortens considerably by simply noting that the sequence m swaps counters 1 and 3.
In the general framework of Graph Theory, R. Wilson gave a complete treatment of puzzles on graphs of which the Lucky 7 is a particular case. Applied to the Lucky 7 puzzle we obtain the following
Theorem
Let n+2 be the number of counters on each of the two puzzle cycles. The total number of counters (including the empty one) is thus 2(n+1). If n is even then the graph is bipartite, and, therefore, puz(Lucky7) has two connected components, one consisting of odd and another of even permutations. If n is odd then puz(Lucky7) is connected, and, therefore the puzzle is solvable for every starting combination.
Reference
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, v1, A K Peters, 2001.
Related material
| |
Sliders and Puzzles on Graphs | |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
71547121