Self-avoiding walk on $\mathbb{Z}$

2012-03-02T15:49:57Z

This one is an unanswered question in Math.SE. I've posted it here because I think it deserves more attention.

How many sequences $\{a_n\}$ exist satisfying:
a) $a_1=0$
b) $\forall k\ge1 $ either $a_{k+1}=a_k+k$ or $a_{k+1}=a_k-k$
c) $a_i \neq a_j$ whenever $i \neq j$
d) $\mathbb{Z}=\{a_i\}_{i > 0}$

Are the two below alternating sequences the only solutions?

$a_{2k}=k$, $a_{2k+1}=-k$
$a_{2k}=-k$, $a_{2k+1}=k$

Also, it is known that Recamán's sequence satisfies

a) $a_1=1$ and b), c) as above

Answer by François Brunault for Self-avoiding walk on $\mathbb{Z}$

2012-03-04T01:44:18Z

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.

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.

The proof consists of the following reductions.

We may assume $s > \frac{b-a}{2}$ and $x < \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<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<\frac{a+b}{2}$.
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$).
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 < L < 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$.

Self-avoiding walk on $\mathbb{Z}$ - MathOverflow

Self-avoiding walk on $\mathbb{Z}$

Answer by François Brunault for Self-avoiding walk on $\mathbb{Z}$