主題
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

使用 探索

參考文獻

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.

在 上被引用

蛇

引用為

Weisstein, Eric W. "Snake." 來自 -- 沃爾夫勒姆網路資源。 https://mathworld.tw/Snake.html

主題分類