Covering a \$d\$-dimensional integer lattice by repeating a minimal set of deterministic moves - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T23:19:51Z http://mathoverflow.net/feeds/question/108085 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108085/covering-a-d-dimensional-integer-lattice-by-repeating-a-minimal-set-of-determin Covering a \$d\$-dimensional integer lattice by repeating a minimal set of deterministic moves T.R. 2012-09-25T18:11:56Z 2012-09-25T23:16:55Z <p>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\$).</p> <p>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.</p> <p>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?</p> <p>Note - The turtle is forbidden from leaving the grid, and any instruction that leads to this will be counted as illegal (not simply ignored).</p> <hr> <p>Let me provide a few trivial examples:</p> <p>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}}.</p> <p>For \$d = 2\$, with a bounded lattice that has dimensions \$N\$ by \$M\$, if \$M &lt; 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?</p> http://mathoverflow.net/questions/108085/covering-a-d-dimensional-integer-lattice-by-repeating-a-minimal-set-of-determin/108116#108116 Answer by Sergei Ivanov for Covering a \$d\$-dimensional integer lattice by repeating a minimal set of deterministic moves Sergei Ivanov 2012-09-25T23:16:55Z 2012-09-25T23:16:55Z <p>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\$.</p> <p>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 <code>\$i&lt;k-1\$</code> and \$X_k\subset X_{k-1}+v\$.</p> <p>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\$.</p> <p>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.</p> <p>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.</p>