Self-avoiding walk on $\mathbb{Z}$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:49:36Z http://mathoverflow.net/feeds/question/90050 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90050/self-avoiding-walk-on-mathbbz Self-avoiding walk on $\mathbb{Z}$ Sidharth Iyer 2012-03-02T15:49:57Z 2012-03-04T08:32:04Z <p>This one is an <a href="http://math.stackexchange.com/questions/111377/self-avoiding-walk-on-mathbbz1.-" rel="nofollow">unanswered question</a> in Math.SE. I've posted it here because I think it deserves more attention.</p> <blockquote> <p>How many sequences $\{a_n\}$ exist satisfying: <p><em>a)</em> $a_1=0$ <p><em>b)</em> $\forall k\ge1$ either $a_{k+1}=a_k+k$ or $a_{k+1}=a_k-k$ <p><em>c)</em> $a_i \neq a_j$ whenever $i \neq j$ <p><em>d)</em> $\mathbb{Z}=\{a_i\}_{i > 0}$</p> </blockquote> <p>Are the two below alternating sequences the only solutions?</p> <ul> <li>$a_{2k}=k$, $a_{2k+1}=-k$</li> <li>$a_{2k}=-k$, $a_{2k+1}=k$</li> </ul> <p>Also, it is known that <a href="http://mathworld.wolfram.com/RecamansSequence.html" rel="nofollow">Recamán's</a> <a href="https://oeis.org/A005132" rel="nofollow">sequence</a> satisfies <p><em>a)</em> $a_1=1$ and <em>b)</em>, <em>c)</em> as above </p> http://mathoverflow.net/questions/90050/self-avoiding-walk-on-mathbbz/90171#90171 Answer by François Brunault for Self-avoiding walk on $\mathbb{Z}$ François Brunault 2012-03-04T01:44:18Z 2012-03-04T08:32:04Z <p>There are many other solutions. As explained in Douglas Zare's comments, the idea is to choose a cell and to make the step large enough in order to visit it.</p> <p>Here are the details (which are best followed with pen and paper...). Suppose that at some time, the convex hull of the integers which are already covered is the interval $[a,b]$. We also assume that we are at one end of the interval, say at $b$, and that we are ready to walk with step $s$. We want to visit a given integer $x \in (a,b)$. We want to do this using only cells at the right of $b$, and in such a way that with one more move, we may reach a cell situated at the left of $a$. By induction, it will then be possible to cover $\mathbf{Z}$. I will write $+$ for moving to the right and $-$ for moving to the left.</p> <p>The proof consists of the following reductions.</p> <ol> <li><p>We may assume $s > \frac{b-a}{2}$ and $x &lt; \frac{a+b}{2}$. Indeed, starting at $b$ with stepsize $s$, do $++(-+)^{s-1}$. We land at $b+3s$ and are ready to walk with step $3s$. The diameter $L=b-a$ and the step $s$ have changed to $(L+3s,3s)$. Thus the ratio $r=L/s$ has changed to $(L+3s)/(3s) = 1+r/3$. Iterating the process, we can make $r$ arbitrarily close to the fixed point $3/2$, in particular we can make $r&lt;2$ which means $s>L/2$ as requested. It is also clear that iterating the process we can make $(x-a)/L$ arbitrary small, in particular we may assume $x&lt;\frac{a+b}{2}$.</p></li> <li><p>We may assume $b-x \equiv 1 \pmod{3}$. Indeed, we may always achieve this during the first reduction, by doing $++(-+)^{s-2}$ or $++(-+)^{s-3}$ instead of $++(-+)^{s-1}$ (which has the effect to land in $b+3s-1$ or $b+3s-2$ instead of $b+3s$).</p></li> <li><p>Let $b-x=3k+1$ with $k \geq 0$. Do $+(+-)^k -$ and you are at $x$, and then do one more step to the left. This works because by assumption $3k &lt; L &lt; 2s$, so we use only cells at the right of $b$, and because when we are at $x$ we have step $s+2k+2>x-a$ which enables to escape at the left of $a$.</p></li> </ol>