Hamiltonian path in bike-lock graph with $1$ known digit

Question

Motivation. My youngest son has a bike lock with dials, and he forgot the unlocking combination completely, except that he remembered that digit $0$ appeared somewhere in the combination. So it was my task to go through all the zillions (but, fortunately, finitely many) possible combinations. Which led to the following problem.

Formal statement. Let $n \geq 2$ be an integer, so we have $n = \{0, \ldots, n-1\}$. For any integer $k>1$ let $$V^0_k = \{x \in n^k: (\exists j\in k)x(j) = 0\}, $$ and let two distinct elements $a\neq b \in V^0_k$ form an edge iff there is $j\in k$ such that

1. $a(i) = b(i)$ for all $i\in n\setminus\{j\}$, and
2. $\{a(j), b(j)\} = \{x, x+1\}$ for some $x\in n-1$, or $\{a(j), b(j)\} = \{0, n-1\}$.

Denote the set of edges by $E_k$.

For what positive integers $k, n$ does the graph $(V^0_k, E_k)$ have a Hamiltonian path? And, if there is a Hamiltonian path, can also a Hamiltonian cycle be found? (The second question doesn't need to be answered for acceptance.)

Answer 1

If $k=2$, then a Hamiltonian path is constructed easily. In the case $k=3$ and $n\equiv1\pmod2$ a Hamiltonian path is constructed as follows: \begin{align*}\label{cycle} %%%%%%%%%%%%%%% x=0 & x_1=0\\ &(0,n-1,n-1)-(0,n-2,n-1)-\ldots-(0,0,n-1)-\\ % z=n-1 -&(0,0,n-2)-(0,1,n-2)-\ldots-(0,n-1,n-2)-\\ % z=n-2 -&(0,n-1,n-3)-(0,n-2,n-3)-\ldots-(0,n-1,n-3)-\\ % z=n-3 &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\ -&(0,0,1)-(0,1,1)-\ldots-(0,n-1,1)-\\ % z=1 -&(0,n-1,0)-(0,n-2,0)-\ldots-(0,0,0)-\\ % z=0 %%%%%%%%%%%%%%% z=0,x\neq0 \\ & x_3=0,\,x_1\neq0\\ -&(1,0,0)-(1,1,0)-\ldots-(1,n-1,0)-\\ % x=1 -&(2,n-1,0)-(2,n-2,0)-\ldots-(2,0,0)-\\ % x=2 &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\ -&(n-2,0,0)-(n-2,1,0)-\ldots-(n-2,n-1,0)-\\ % x=n-2 -&(n-1,n-1,0)-(n-1,n-2,0)-\ldots-(n-1,0,0)-\\ % x=n-1 %%%%%%%%%%%%%%% y=0 \\ & x_2=0,x_1\neq0,x_3\neq0\\ -&(n-1,0,1)-(n-1,0,2)-\ldots-(n-1,0,n-1)-\\ % x=n-1 -&(n-2,0,n-1)-(n-2,0,n-2)-\ldots-(n-2,0,1)-\\ % x=n-2 &\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\ -&(2,0,n-1)-(2,0,n-2)-\ldots-(2,0,1)-\\ % x=2 -&(1,0,1)-(1,0,2)-\ldots-(1,0,n-1). % x=1 \end{align*} In this table, the points are written out in the order they are traversed. The little comments make the table easier to read (I think so). If $n\equiv0\pmod2$, then the Hamiltonian path is constructed similarly. It seems to me that in the case $k>3$ the Hamiltonian path can also be constructed in a similar way.

Edit.

I tried to make the above Hamiltonian path more visual. The picture shows all vertices of the two graphs at $n=9$ and $n=10$ and almost all edges. Only edges of type $(0,i,j)-(n-1,i,j)$ are not shown. We see that the Hamiltonian path exists without these edges.

Answer 2

Partial answer to the cycle version.

Case $k=2$, any $n$: The graph has no Hamiltonian cycle. If $n \ge 3$, the graph consists of two $n$-cycles that intersect at a single point $(0,0)$. If $n=2$, the graph is just the chain $(0,1),(0,0),(1,0)$.

---

Case $k \ge 3$ and $n$ even: The graph has no Hamiltonian cycle. This is because the graph is bipartite and $|V|$ is odd, and you cannot have an odd-length cycle with two alternating colors.

• To see that it is bipartite, color each vertex blue if the sum of coordinates is even, and red if the sum of coordinates is odd; every edge in the graph moves just one coordinate, either between $i$ and $i+1$ (different parities), or between $n-1$ (odd) and $0$ (even), so it flips the color.
• To see that $|V|$ is odd, note that $V = A \setminus B$, where $A = \{0,1,\ldots,n-1\}^k$, that is all $k$-digit strings, and $B = \{1,2,\ldots,n-1\}^k$, that is all $k$-digit strings without zeros. Clearly $|V|=|A|-|B|$, with $|A|$ even and $|B|$ odd, so $|V|$ is odd.

---

Case $k \ge 3$ and $n$ odd: Computations suggest that there is a Hamiltonian cycle, but this is inconclusive. I have verified by straightforward SageMath code with $k=3$ up to $n=11$, and with $(k,n) \in \{(4,3),(4,5),(5,3)\}$.

Now the bipartity argument does not apply, because $0$ and $n-1$ have same parity, so the wraparound edges make the graph non-bipartite. (The wraparound possibility is essential; if we leave out the wraparound edges, there is again no Hamiltonian cycle, because the graph is again bipartite and has odd number of vertices.)

Here is an example solution with $k=3$, $n=5$. Green lines indicate wraparound between $0$ and $4$. I don't see any glaring structure in the machine-generated solution, so it is difficult to generalize from that.

000-040-140-240-340-300-310-410-420-320-
220-210-110-100-104-103-003-403-404-304-
303-302-301-201-200-204-203-202-102-101-
001-041-031-030-020-120-130-230-330-430-
440-400-401-402-002-012-013-023-033-043-
042-032-022-021-011-010-014-024-034-044-
004

Update. Here is a manually designed solution for $k=3$, $n=7$. From the picture it is probably clear how it generalizes to any odd $n$. Interestingly, we only need to do one wraparound.