主题
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 移动

使用 Wolfram|Alpha 探索

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.

在 Wolfram|Alpha 上引用

Baguenaudier

请引用本文为

Weisstein, Eric W. "Baguenaudier." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Baguenaudier.html

学科分类