主題
Search

Baguenaudier

ChineseRings

一種謎題，涉及從環狀雙杆中解開一組環，最初由法國農民用於鎖箱子 (Steinhaus 1999)。 “Baguenaudier”在法語中意為“浪費時間的人”，這個謎題也稱為中國環或魔鬼針謎題。（“Bague”也意為“環”，但這似乎是一個詞源上的巧合。有趣的是，決明樹在法語中也稱為“baguenaudier”。） Culin (1965) 將這個謎題歸功於中國將軍洪明（公元 181-234 年），他將其作為禮物送給妻子，以便在她在他外出征戰時打發時間。

Baguenaudier 謎題的解法與 格雷碼 理論密切相關。

對於 n 個環，所需的最小移動次數 a(n) 是

a(n)=[2/3(2^n-1)]
(1)
={1/3(2^(n+1)-2) n even; 1/3(2^(n+1)-1) n odd,
(2)

其中 [x] 是向上取整函式，給出 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, ... (OEIS A000975)。這些數字的生成函式是

1/((1-2x)(1-x^2))=1+2x+5x^2+10x^3+21x^4+....
(3)

它們也由遞推關係給出

a(n)=a(n-1)+2a(n-2)+1
(4)

其中 a(1)=1 和 a(2)=2。

透過同時移動兩個端環，n 個環的移動次數可以減少到

b(n)={2^(n-1)-1 n even; 2^(n-1) n odd,
(5)

給出 1, 1, 4, 7, 16, 31, 64, 127, 256, 511, ... (OEIS A051049)。

將解法的複雜度定義為環從最後一個環到謎題底座的弧線透過的最小次數，解法的最小複雜度是 2^(n-1)，正如 Kauffman (1996) 推測並由 Przytycki 和 Sikora (2000) 證明的那樣。

另請參閱

格雷碼, Habiro 移動

使用 探索

WolframAlpha

更多嘗試

參考文獻

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." Quantum 6, 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."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.

在 上引用

Baguenaudier

請引用本文為

Weisstein, Eric W. "Baguenaudier." 來自 Web 資源。 https://mathworld.tw/Baguenaudier.html

學科分類