Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves

2012-09-25T18:11:56Z

Imagine I place a turtle on some desired vertex, $v_i$, of a bounded $d$-dimensional integer lattice, $Z^d$, with dimensions $(l_1, ..., l_d)$. The turtle is able to travel from vertex to vertex along the edges of the lattice, but is forbidden from ever returning to a previously visited vertex (i.e. it "burns" the vertices it visits with probability $p = 1$).

We want to teach the turtle to cover the $d$-dimensional integer lattice by repeating a series of $P$ deterministic moves along the set of $2*d$ possible direction vectors. For example, in two-dimensions ($d = 2$), we might label the four possible directions in which the turtle can move as $(N, W, E, S)$ and train the turtle with an instruction set like the following: {{Step 1, GO NORTH}, {Step 2, GO SOUTH}, ..., {Step P, GO SOUTH}, {GOTO Step 1}}. With the right instruction set, after some number of GOTO loops, the turtle will visit all possible vertices and quit.

Provided that the turtle can be initialized anywhere one desires on the lattice, and provided dimensions of the $d$-dimensional integer lattice, $(l_1, ..., l_d)$, what is the smallest value of $P$ that permits the turtle to cover the lattice?

Note - The turtle is forbidden from leaving the grid, and any instruction that leads to this will be counted as illegal (not simply ignored).

Let me provide a few trivial examples:

For $d = 1$, the optimal solution is to place the turtle at the far left or right-side of the lattice, and then (assuming the turtle is placed on the far left), program the turtle with the two-line $(P = 1)$ instruction set: {{Step 1, GO RIGHT}, {GOTO Step 1}}.

For $d = 2$, with a bounded lattice that has dimensions $N$ by $M$, if $M < N$, we can program the turtle to: (1) first move from $(i, 1)$ to $(i, M)$, (2) move from $(i, M)$ to $(i+1, M)$, (3) move from $(i+1, M)$ to $(i+1, 1)$, and finally (4) move from $(i+1, 1)$ to $(i+2, 1)$, then GOTO (1) until we sweep through the 2D lattice. This constitutes a value of $P = (M - 1) + 1 + (M - 1) + 1 = 2M$. I wonder if it's possible to do better?

Answer by Sergei Ivanov for Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves

2012-09-25T23:16:55Z

Yes your example is optimal provided that the longest side is longer than 2. Let me stick to dimension 2, the higher dimensions are similar. I assume the vertices have integer coordinates $(i,j)$, $1\le i\le M$, $1\le j\le N$.

The turtle changes its position by a fixed vector $v$ after each cycle of execution. Let $X_1$ be the set of first $P$ vertices visited, $X_2$ the set of vertices from $(P+1)$-th to $(2P)$-th, and so on. The last set $X_k$, $k=[MN/P]$, may contain fewer than $P$ vertices if the last cycle is not executed completely. Note that $X_{i+1}=X_i+v$ (i.e., the translation of $X_i$ by $v$) for every $i<k-1$ and $X_k\subset X_{k-1}+v$.

First observe that $v$ cannot have two nonzero coordinates if $P\le MN/2$. Indeed, assume w.l.o.g. that both coordinates are positive. Then consider the corner $c=(1,N)$. It must belong to $X_1$ because $c-v$ is outside the grid. Since $c+v$ is also outside the grid, $X_2$ is incomplete, so $P>MN/2$.

The case $v=(0,1)$ or $v=(1,0)$ is impossible (if $M,N>1$). Indeed, suppose that $v=(0,1)$. Then every vertex $x$ of the form $(i,1)$, $1\le i\le M$, belongs to $X_1$ because $x-v$ is outside the grid. Then $x+v$ belongs to $X_2$, $x+2v$ belongs to $X_3$ and so on. Therefore no points other than $(i,1)$ belong to $X_1$. Let $x_0$ be the original vertex, then $x_0+v$ is the first visited vertex of $X_2$. So the $P$-th move is from some point of $X_1$ to $x_0+v$. But in $X_1$ only $x_0$ lies at distance 1 from $x_0+v$, a contradiction.

So $v$ has a form $(0,m)$ or $(m,0)$ where $m\ge 2$. Then a similar analysis show that $X_1$ consists of first $m$ rows or columns of the grid, so $P=mM$ or $P=mN$. Therefore $m=2$ and $P=2M$ is optimal.

Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves - MathOverflow

Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves

Answer by Sergei Ivanov for Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves