# A note on the snake-in-the box problem

C. Ramanujacharyulu, V. V. Menon

► To cite this version:

C. Ramanujacharyulu, V. V. Menon. A note on the snake-in-the box problem. Annales de l'ISUP, 1964, XIII (2), pp.131-135. hal-04085176

HAL Id: hal-04085176

https://hal.science/hal-04085176

Submitted on 28 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A NOTE ON THE SNAKE - IN - THE BOX PROBLEM

C. RAMANUJACHARYULU et V. V. MENON

## 1. Introduction

Let us consider $G_n$, the set of all n-digit binary sequences with addition modulo 2 (i.e. placewise with $0+0=1+1=0$, $0+1=1+0=1$). Two elements of $G_n$ are adjacent if their sum (mod 2) has just one digit which is 1. A snake is a sequence of elements of $G_n$ such that

a) each element of the sequence (except the last) is adjacent to the element that follows it;

b) the last element of the sequence is adjacent to the first;

c) no element of the sequence is adjacent to more than two elements of the sequence.

The problem is to find the largest number of elements that a snake can contain. It arises in the study of error correcting codes. This problem is studied by W.H. Kautz [2] on unit distance error checking codes.

Taking the problem into graph theory it reduces to finding the largest elementary cycle without chords in the unit n-dimentional hypercube.

It was conjectured that this number is

$$3 + \frac{2^n - (-1)^n}{3},$$

but Shimon Even in a recent paper ([3])

shows that the conjecture is false, since there exist a snake of length 26 for n = 6, and a snake of length 48 for n = 7.
The purpose of the present note is to give an upper bound to the number of vertices a snake can contain, and a lower bound for the number of vertices in the longest snake. The former is by C. Ramanujacharyulu and the latter by V.V. Menon.

*Acknowledgement* : The authors are grateful to the referee for having drawn their attention to the references [2] and [3], and to the co-mité the Rédaction for their suggestions in improving the paper. They express their indebtedness to Professor Claude Berge for his encouragement.

## 2. Definitions

Let G be an unoriented graph (X,U) (See [1]).

2.1. CYCLE : In a graph G a sequence of arcs (u₁,u₂,...,uₖ,...,uq) is called a cycle if

(1) every arc uₖ (1 < k < q) is joined to uₖ-₁ by one of its extremities and to uₖ+₁ by the other extremity,

(2) no arc is used twice,

(3) the initial vertex of u₁ coincides with the terminal vertex of uq.

An elementary cycle is a cycle which further satisfies that in describing the cycle we cannot encounter the same vertex once again (except the initial and the terminal vertices which coincide).

2.2. CHORD : An edge is a chord with respect to a cycle C if the edge joins two nonconsecutive vertices of the cycle C.

Let us construct a graph G where the vertices represent the 2ⁿ, n-digit binary sequences. An edge appears in the graph if the corresponding binary sequences are adjacent. Now we find that the snake-in-the-box problem identifies itself with the problem of finding the cycle with maximum number of vertices and without chords.

## 3. An upper bound for the snake

Considering the constructed graph, the following properties of it are apparent :

3.1. each vertex is joined to n vertices exactly ;
3.2. there are no cycles of length 2 or 3;

3.3. given two vertices each of which is adjacent to a given vertex, there is exactly one more vertex which is adjacent to each of these two.

3.4. through each vertex there are $\binom{n}{2} = \frac{1}{2} \cdot n \cdot (n-1)$ cycles each of length 4, through it.

For, through any vertex there are exactly n edges. Each pair of these edges gives rise to a four-cycle (a cycle of length four) in view of the property 3.3;

3.5. the total number of four-cycles is $\binom{n}{2} \cdot 2^{n-2}$

For, through each vertex there are $\binom{n}{2} 2^n$ four-cycles. But each four-cycle is counted four times, once at each of its vertices. Hence the number of distinct four-cycles is $\binom{n}{2} \cdot 2^{n-2}$.

Now assume that a snake containing v vertices exists. Evidently (if $n > 2$) each four-cycle can contribute at most three vertices to the snake, for otherwise one of these vertices would be adjacent to more than two vertices in the snake. Thus there could be at most $3 \cdot \binom{n}{2} \cdot 2^{n-2}$ vertices contributed by the four-cycles to the snake. We note, however, that in this counting each vertex is counted as many times as there are four-cycles through it, i.e., $\binom{n}{2}$ times. Thus v is at most equal to $3 \cdot 2^{n-2}$.

### 4. A lower bound for the length of a longest snake

In this section we establish the following result:

"Let $a_1, a_2, \dots, a_{u_n}, a_1$ be a snake in $G_n$. Then there exists a snake in $G_{n+1}$ whose length is at least $\frac{3}{2} \cdot u_n - 1$."

Using this result and the fact that the length of a snake is an even number, we can easily build up a lower bound for the length of a longest snake, knowing this length for $G_5$, for example.
The above result is proved by actually constructing a snake in $G_{n+1}$ as follows. We denote by $a_i0$ the $(n+1)$-length sequence whose first $n$ positions are occupied by the sequence $a_i$ and the $n+1$st position is occupied by $0$. Similarly we denote by $a_i1$ the point in $G_{n+1}$ whose first $n$ positions constitute $a_i$ and the $n+1$st position is occupied by $1$. We consider the subgraph formed by the $2u_n$ points

$$a_10, a_20, \dots, a_{u_n0},$$

$$a_1, a_2, \dots, a_{u_n1}.$$

Since $a_1, a_2, \dots, a_{u_n}, a_1$ is a snake in $G_n$, it is easy to verify that $a_i0$ is joined by an edge to $a_i1, a_{i-1}0$ and $a_{i+1}0$ and to no other points (for $i = 2, 3, \dots, m$), and $a_10$ is joined by an edge to $a_11, a_20$ and $a_{u_n}0$ only. In other words, the subgraph looks as follows.

<figure><img src="image_2.png" /><figcaption>Fig. 1</figcaption></figure>

We now delete the points

$$a_21, a_40, a_61, a_80, \dots, a_{4m}0, a_{4m+2}1, \dots$$

If $u_n \equiv 0 \mod 4$, then the last point to be deleted is $a_{u_n}0$, and the remaining points determine a subgraph which is evidently a snake.
If $u_n \equiv 2 \mod 4$, then the last point to be deleted is $a_{u_n 1}$;
in this case we also delete $a_1$ and the remaining points determine
a subgraph which is a snake.

We thus get a snake of length $\frac{3}{2} u_n$ if $u_n \equiv 0 \mod 4$; and
of length $\frac{3}{2} u_n - 1$ if $u_n \equiv 2 \mod 4$, in the graph $G_{n+1}$.

[It is easy to see that in the graph $G_n$, there cannot exist cycles of odd length].

5. Remarks

(1) It is possible to improve both the upper and the lower bounds considerably if one could estimate the number of points in a longest snake which are at a distance of two from a given point a in the snake, i.e. the n-length sequences which differ from a in exactly two positions and which belong to the snake.

(2) The bounds given are very wide. For example, when $n=5$, the upper bound is $3.2^{5-2} = 24$ while the actual value is 14. On the other hand, the lower bound is (since the value is 8 for $n=4$).

$\frac{3}{2} \cdot 8 = 12$, whereas the actual value, as noted above, is 14.

REFERENCES

[1] BERGE (C.): *Théorie des graphes et ses applications*. Paris, Dunod (1960).

[2] KAUTZ (W. H.): Unit-distance error-checking codes, *I.R.E. Trans. Electronic Computers* **7** (1958), 179-180

[3] EVEN (S.): *Snake-in-the-box Codes, I.E.E.E. Trans. Electronic Computers* **12** (1963), 18-18.

Indian Statistical Institute
Calcutta, Inde

Reçu le 20 Octobre 1963

Révisé le 10 Décembre 1963

<figure><img src="image_3.png" /></figure>

0,
tly