15
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I've fixed some of the latex. Would you mind to choose the same title as on stackexchange? I think "Self-avoiding walk on $\mathbb{Z}$" is quite informative compared to "How many sequences exist such that:" $\endgroup$
    – Martin Brandenburg
    Mar 2, 2012 at 16:23
  • 3
    $\begingroup$ I would be very surprised if those were the only solutions. I think you have enough flexibility to extend partial solutions by using a long sequence of $+$s followed by a long sequence of $-$s (or vice versa) to fill in an arbitrary uncovered integer. $\endgroup$
    – Douglas Zare
    Mar 2, 2012 at 16:29
  • 3
    $\begingroup$ It's really easy to get yourself stuck as you go down a path you've already gone up. Just end up halfway in between two points of distance $s$. You have to be careful to avoid this. $\endgroup$
    – Will Sawin
    Mar 2, 2012 at 21:51
  • 2
    $\begingroup$ @Douglas Zare: But what is the patch around the origin, and how will its size grow relative to the step size. Say, if one would start with a long sequence of +, say n steps; one would be at around n^2/2 eventually I want to go back suppose just with -. Then I'd need still something like (sqrt(2)-1)n steps. Or I need to make order sqrt(x) steps through some area of size x where order sqrt(x) are already forbidden. This seems already rather 'risky'. Of course one has some back and forth option, so this might all work. But in any case the 'margin' with which this might work seems not huge. $\endgroup$
    – user9072
    Mar 3, 2012 at 2:06
  • 3
    $\begingroup$ Property (d) doesn't seem to be known for Recaman's sequence -- at least according to the links given in the question. $\endgroup$
    – François Brunault
    Mar 4, 2012 at 0:16

1 Answer 1

Reset to default
11
$\begingroup$

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.

  1. 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}$.

  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$).

  3. 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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice! Looks good to me. $\endgroup$
    – George Lowther
    Mar 4, 2012 at 2:09
  • $\begingroup$ ...except, I think you should have $+(+-)^k-$ in step 3, and you are at $x$. $\endgroup$
    – George Lowther
    Mar 4, 2012 at 2:10
  • $\begingroup$ @George : You're right, thanks, it's corrected now. $\endgroup$
    – François Brunault
    Mar 4, 2012 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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