A snake is an Eulerian path in the 
-hypercube that has no chords
(i.e., any hypercube edge joining snake vertices is
a snake edge). Klee (1970) asked for the maximum length 
of a 
-snake.
Klee (1970) gave the bounds
 |
(1)
|
for 
(Danzer and Klee 1967, Douglas
1969), as well as numerous references. Abbott and Katchalski (1988) show
 |
(2)
|
and Snevily (1994) showed that
 |
(3)
|
for 
, and conjectured
 |
(4)
|
for 
. The first few values for 
for 
, 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).
in the 
-Cube." J. Combin. Th. 6,
323-339, 1969.Emelianov, P. "Snake-in-the-Box." 
-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 
-Dimensional Snake?" Amer. Math. Monthly 77,
63-65, 1970.Sloane, N. J. A. Sequence 
-Dimensional Cube." Diskret. Analiz. 45,
1987.