主题
Search

蛇

蛇是 欧拉路径 在 d-超立方体 中，它没有弦（即，连接蛇顶点的任何 超立方体 边都是蛇边）。Klee (1970) 询问了 s(d) 的最大长度 d-蛇。Klee (1970) 给出了界限

7/(4(d-1))<=(s(d))/(2^d)1/2-(1-12/2^(-d))/(7d(d-1)^2+2)
(1)

对于 d>=6 (Danzer and Klee 1967, Douglas 1969)，以及许多参考文献。Abbott 和 Katchalski (1988) 表明

s(d)>=77·2^(d-8),
(2)

Snevily (1994) 表明

s(d)>=2^(d-1)(1-1/(20d-41))
(3)

对于 d<=12，并推测

s(d)>=3·2^(d-3)+2
(4)

对于 d<=5。s(d) 对于 d=1, 2, ..., 的前几个值是 2, 4, 6, 8, 14, 26, ... (OEIS A000937)。

另请参阅

Apple Surface, Hypercube, Snake Eyes, Snake Lemma, Snake Oil Method, Snake Polyiamond

使用 Wolfram|Alpha 探索

参考文献

Abbott, H. L. and Katchalski, M. "On the Snake in the Box Problem." J. Combin. Th. Ser. B 44, 12-24, 1988.Danzer, L. and Klee, V. "Length of Snakes in Boxes." J. Combin. Th. 2, 258-265, 1967.Douglas, R. J. "Some Results on the Maximum Length of Circuits of Spread k in the d-Cube." J. Combin. Th. 6, 323-339, 1969.Emelianov, P. "Snake-in-the-Box." http://mix.nsk.ru/epg/snake.html.Evdokimov, A. A. "Maximal Length of a Chain in a Unit n-Dimensional Cube." Mat. Zametki 6, 309-319, 1969.Guy, R. K. "Unsolved Problems Come of Age." Amer. Math. Monthly 96, 903-909, 1989.Guy, R. K. "Monthly Unsolved Problems." Amer. Math. Monthly 94, 961-970, 1989.Guy, R. K. and Nowakowski, R. J. "Monthly Unsolved Problems, 1696-1995." Amer. Math. Monthly 102, 921-926, 1995.Kautz, W. H. "Unit-Distance Error-Checking Codes." IRE Trans. Elect. Comput. 7, 177-180, 1958.Klee, V. "What is the Maximum Length of a d-Dimensional Snake?" Amer. Math. Monthly 77, 63-65, 1970.Sloane, N. J. A. Sequence A000937/M0995 in "The On-Line Encyclopedia of Integer Sequences."Snevily, H. S. "The Snake-in-the-Box Problem: A New Upper Bound." Disc. Math. 133, 307-314, 1994.Solov'jeva, F. I. "An Upper Bound for the Length of a Cycle in an n-Dimensional Cube." Diskret. Analiz. 45, 1987.

在 Wolfram|Alpha 上被引用

蛇

引用为

Weisstein, Eric W. "Snake." 来自 MathWorld -- 沃尔夫勒姆网络资源。 https://mathworld.net.cn/Snake.html

主题分类