6
$\begingroup$

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.)

$\endgroup$
8
  • 3
    $\begingroup$ Do you want a Hamiltonian cycle (as suggested in the title) or a Hamiltonian path (as suggested in the question)? $\endgroup$ May 17 at 12:08
  • $\begingroup$ Good point @DustinG.Mixon -> I would already be happy with a path, but a cycle would even be nicer. I will edit the question accordingly. $\endgroup$ May 18 at 6:14
  • 1
    $\begingroup$ The bike lock task seems to motivate the path version (why would one need to return to the first combination?), but the cycle version is probably harder. $\endgroup$ May 18 at 7:35
  • $\begingroup$ That's right @JukkaKohonen, I modified the question accordingly and was just wondering about cycles additionally. But the path question is closest to my heart, so to say. $\endgroup$ May 18 at 8:05
  • 1
    $\begingroup$ Thanks :) Perhaps we will yet see the ultimate answer that addresses all $k$ and $n$. $\endgroup$ May 24 at 16:16

2 Answers 2

5
$\begingroup$

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. enter image description here

$\endgroup$
2
$\begingroup$

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

Bike lock solution with k=3, n=5

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.

Bike lock solution with k=3, n=7

$\endgroup$
1
  • 1
    $\begingroup$ The last figure is very clear! $\endgroup$
    – kabenyuk
    May 24 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.