Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
What happens if an instruction directs the turtle outside the grid, or to a previously visited vertex? Are such instructions forbidden, or are they allowed but not followed? –  Sergei Ivanov Sep 25 '12 at 19:37
    
@Sergei Ivanov, Please see the note I've added to the question. No instruction is allowed to direct the turtle off of the grid prior to coverage. –  T.R. Sep 25 '12 at 20:12
    
@T.R.: I think you need to detail more information about what information the turtle has access to. Does it know the dimensions of the box? Does it know its own location? Can it sense when it is on the box boundary? Can it inspect its neighbors to see which have been visited? –  Joseph O'Rourke Sep 25 '12 at 21:21
    
@Joseph O'Rourke, Sorry, I should have been much clearer with the problem specification. The idea is that you have total information about the grid, control over where the turtle is placed, and the ability to program the turtle. The challenge is to minimize the length of the loop that governs its motions on the lattice while still insuring coverage under the constraint that no vertex can be re-visited. –  T.R. Sep 25 '12 at 21:45
    
It might have been better to call the turtle a robot. It simply executes a set of programmed moves over and over again until it covers the lattice. –  T.R. Sep 25 '12 at 21:48
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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