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

How many sequences $a_1,a_2,a_3,\dotsc$, satisfy:
i) $a_1=0$
ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$)
iii) $a_i\neq a_j$ for $i\neq j$
iiii) $\mathbb{Z}=\{a_i\}_{i>0}$

Are the two alternating sequences the only solutions?

$a_1,a_2,a_3,..=0,1,-1,2,-2,3,-3,4,...$
or
$a_1,a_2,a_3,..=0,-1,1,-2,2,-3,...$

Is there a sequence satsifying i),iii),iiii) and ii) ($a_{n+1}=a_n-n^2$ or $a_{n+1}=a_n+n^2$) ?

• A similar question, but for positive sequences, is given at oeis.org/A005132 – Gerry Myerson Feb 20 '12 at 23:17
• You're telling me that mmm asked a question and LLLLL is awarding a bounty on it? – Graphth Feb 22 '12 at 19:38
• We could ask $\kappa\kappa\kappa\kappa\kappa\kappa\kappa$ for a solution? – draks ... Feb 24 '12 at 7:36
• @LLLLL: Computational evidence? You have a sequence other than these two containing all of $\mathbb{Z}$? What is your evidence? – TMM Feb 29 '12 at 18:16

Only uncountably many. See this link to MO.

Two obvious solutions are :-

1. 0, 1, 3, 6, 10, 15, ... an = Sigma(n-1)

2. 0, -1, -3, -6, -10, -15, ... an = -Sigma(n-1)

Here, I am considering only one of the Formulae at a time. Either an = a(n-1) - n OR an = a(n-1) + n for all the numbers in the series. And of course, here ai != aj (for i != j)

Now, considering the solutions that you gave :

$a_1,a_2,a_3,..=0,1,−1,2,−2,3,−3,4,...$

AND

$a_1,a_2,a_3,..=0,−1,1,−2,2,−3,...$

Here, you have used both the formulae in alternate fashion, starting from either one of them and thereby getting two series.

Now, consider an = a(n-1) - n as "Going Backwards" AND

an = a(n-1) + n as "Going Forwards".

Observe one solution below :-

$0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, ...$

Here I go forward 3 times, till I reach $6$ and then toggle between going backwards and going forwards from then on. Since my first few (say r) steps were forward, it could be possible that going backwards from some ak could lead to a number which already exists in the series and thereby violating the condition ai !+ aj (For i != j). Whenever such violation occurs, I would forward once again and then try to go backwards and the process continues.

Similarly, we can also go backwards a few steps (more specifically more than 1 step), and then keep toggling. Whenever there is a violation, we go back once again and try to come forward and the process continues.

When our initial step (before toggling) is only 1 time, then we get the two solutions that you gave. And there is no conflict in any step in that case. This can be generalized to going in one direction for r times, and then toggling. This would lead to INFINITE SUCH SERIES, since r E N (Natural Numbers) which are infinite.

However, this is only one such set of infinte series. We could go in any different fashion as follows :

$0, 1, 3, 6, 2, -3, -9, ...$(Going forward till 6 and then going back)

Or it can be any other random order too.

So, the possible number of sequences that satisfy all 4 conditions would be INFINITE.

And for the answer to the second question, series satisfying an+1=an−n2 or an+1=an+n2,

Following two are again the obvious solutions :

$1. 0, 1, 5, 14, ...$(Going forward)
$2. 0, -1, -5, -14, ...$ (Going backward)

• Your solutions do not satisfy the fourth condition above (they are not surjective onto $\mathbb{Z}$). – Brandon Carter Feb 24 '12 at 7:39
• @BrandonCarter Does it mean that all the integers must be one of the element of the series? – whitehat Feb 24 '12 at 8:08
• @user840077 Yes. – TROLLHUNTER Feb 24 '12 at 8:37
• And it's a bit of a nitpick, but "infinite" is not a cardinal number. There are two infinite cardinal numbers that could answer the question: $\aleph_0$ and $2^{\aleph_0}$. – Tanner Swett Feb 27 '12 at 0:31
• @DejanGovc: Wrong. The set of such sequences is a Borel (in fact, $G_\delta$) subset of a Polish space, hence it is either countable or of cardinality $2^{\aleph_0}$. – Emil Jeřábek Mar 2 '12 at 16:16