Below is a discussion of
the mathematical Baguenaudier -- M. Gardner is among the cited references. There
is a picture in that book and another can be seen at http://mathworld.wolfram.com/Baguenaudier.html.
The "Baguenaudier sequence" is closely related to the Fibonacci
sequence, which in turn in closely related to "Phi" (IPH?) and the gnomon
mentioned by Van somewhere along with the Euler problem.
I do wish
someone more mathematically inclined than I am would investigate
this.
Carolyn
Baguenaudier
A puzzle involving disentangling a set of
rings from a looped double rod, originally used by French peasants to lock
chests (Steinhaus 1999). The word "baguenaudier" means "time-waster" in French,
and the puzzle is also called the Chinese rings or Devil's needle puzzle.
("Bague" also means "ring," but this appears to be an etymological
coincidence. Interestingly, the bladder-senna tree is also known as
"baguenaudier" in French.) Culin (1965) attributes the puzzle to Chinese general
Hung Ming (A.D. 181-234), who gave it to his wife as a present to occupy her
while he was away at the wars.
The solution of the baguenaudier is
intimately related to the theory of Gray codes.
The minimum
number of moves a(n) needed for n rings is
(1)
where is the ceiling function, giving 1, 2, 5, 10,
21, 42, 85, 170, 341, 682, ... (Sloane's A000975). The generating
function for these numbers is (2)
They are also given by the
recurrence relation (3)
with and .
By
simultaneously moving the two end rings, the number of moves for n rings
can be reduced to (4)
Defining the complexity of a solution as
the minimal number of times the ring passes through the arc from the last ring
to the base of the puzzle, the minimal complexity of a solution is , as
conjectured by Kauffman (1996) and proved by Przytycki and Sikora (2000).
Gray Code, Habiro Move
References
Culin, S.
"Ryou-Kaik-Tjyo--Delay Guest Instrument (Ring Puzzle)." §20 in Games of the
Orient: Korea, China, Japan. Rutland, VT: Charles E. Tuttle,
pp. 31-32, 1965.
Dubrovsky, V. "Nesting Puzzles, Part II: Chinese
Rings Produce a Chinese Monster." Quantum6, 61-65 (Mar.) and
58-59 (Apr.), 1996.
Elliott Avedon Museum and Archive of Games,
University of Waterloo, Ontario, Canada. "Wire and Ring Puzzles."
http://www.ahs.uwaterloo.ca/~museum/puzzles/wire/.
Gardner, M.
"The Binary Gray Code." In Knotted Doughnuts and Other Mathematical
Entertainments. New York: W. H. Freeman, pp. 15-17, 1986.
Kauffman, L. H. "Tangle Complexity and the Topology of the Chinese
Rings." In Mathematical Approaches to Biomolecular Structure and
Dynamics. New York: Springer-Verlag, pp. 1-10, 1996.
Kraitchik,
M. "Chinese Rings." §3.12.3 in Mathematical Recreations. New York:
W. W. Norton, pp. 89-91, 1942.
Przytycki, J. H. and
Sikora, A. S. "Topological Insights from the Chinese Rings." 21 Jul 2000.
http://arXiv.org/abs/math.GT/0007134/.
Sloane, N. J. A.
Sequences A000975 and A051049 in "The On-Line Encyclopedia of
Integer Sequences." http://www.research.att.com/~njas/sequences/.
Slocum, J. and Botermans, J. Puzzles Old and New: How to Make and
Solve Them. Seattle, WA: University of Washington Press, p. 105, 1988.
Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover,
pp. 268-269, 1999.