# A sequence $a_i$ such that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also permutation of the positive integers

Let $a_1,a_2,\ldots,$ be a permutation of the positive integers. Is it possible that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also a permutation of the positive integer?

My idea is to construct the sequence in such a way that every $a_i$ and $|a_i-a_{i+1}|$ occurs, and never repeats. So I start with $a_1=1$. At any stage, if the lowest unused $a_i$ is $m$ and the lowest unused difference $|a_i-a_{i+1}|$ is $n$, we will attempt to use them. Suppose we've constructed the sequence up to $a_i$. Then set $a_{i+1}$ to be something sufficiently high, set $a_{i+2}=a_{i+1}+n$, and $a_{i+3}=m$. Then we've used $m$ and $n$.

Does this work?

• What if the difference $|m-a_{i+2}|$ has already been used? – Brian M. Scott Nov 15 '14 at 21:40
• @BrianM.Scott I also need to choose $a_{i+1}$ large enough so that the difference $|m-a_{i+2}|=|m-a_{i+1}-n|$ has not been used. Thanks. – Dexter Nov 15 '14 at 21:44
• Your question mentions $|a_i-a_j|$, twice. But from the formulation I gather that only adjacent differences $|a_i-a_{i+1}|$ are taken into consideration. Did I misread the question? – Marc van Leeuwen Nov 15 '14 at 22:42
• @MarcvanLeeuwen I meant $|a_i-a_{i+1}|$ all along. Thanks for alerting me to that. – Dexter Nov 15 '14 at 22:52

This will work, though it may need some minor tweaks for the edge cases.

The only tweak-needing edge case I can see is if $a_i+n=m$ already. In that case, no matter how large you choose $a_{i+1}$ you would get $|a_{i}-a_{i+1}|=|a_{i+2}-a_{i+3}|$. But of course that is easy to correct for: just choose $a_{i+1}=m$ right away and continue from there two numbers ahead!

(Complete rewrite after Henning Makholm's observation)

Yes, this seems to work if we make the procedure a little bit less handwavy:

We want a sequence $(a_n)$ such that the map $\mathbb N\to\mathbb N$, $n\mapsto a_n$ is bijective and also the map $\mathbb N\to\mathbb N$, $n\mapsto |a_{n+1}-a_n|$ is bijective (injectivity of the first map guarantees that the second map really goes to $\mathbb N$ instead of $\mathbb N_0$). Especially, we have countably many tasks of the form "please ensure that $m$ occurs as term in the sequence" and "please ensure that $m$ occurs as differnce of consecutive terms of the sequence", in some order enumerated as $T_1, T_2, \ldots$.

Definition. For $n\in\mathbb N_0$, call a sequence $a_1,\ldots, a_{2n}$ of $2n$ naturals suitable if

1. $a_i\ne a_j$ for $1\le i<j\le 2n$
2. $|a_{i+1}-a_i|\ne |a_{j+1}-a_j|$ for $1\le i<j<2n$
3. The first $n$ tasks are fulfilled (i.e. for $1\le k\le n$, if task $T_k$ is "include $m$ as term" then $a_i=m$ for some $i$ with $1\le i\le 2n$, and if task $T_i$ is "include $m$ as difference" then $|a_{i+1}-a_i|=m$ for some $i$ with $1\le i<2n$)

Claim. Any suitable sequence $a_1,\ldots,a_{2n}$ of length $2n$ ($n\in\mathbb N_0$) can be extended to a suitable sequence $a_1,\ldots,a_{2n+2}$ of length $2(n+1)$.

Proof. Let $N$ be a sufficiently big natural number. Specifically, we assume that $a_i<N$ for $1\le i\le 2n$. Consequently, $|a_{i+1}-a_i|<N$ for $1\le i<2n$ as well.

• If $T_{n+1}$ is already fulfilled by $a_1,\ldots, a_{2n}$, then the condition 3 of the definition is fulfilled no matter how we extend the sequence. We can let $a_{2n+1}=2N$ and $a_{2n+2}=4N$, which clearly ensures 1 and also 2 (because $N<|a_{2n+1}-a_{2n}|<2N=|a_{2n+2}-a_{2n+1}|$).
• Otherwise, if $T_{n+1}$ asks to include $m$ as term, let $a_{2n+1}=2N+m$ and $a_{2n+2}=m$. Clearly, condition 3 is satisfied by this. Condition 1 is satisfied because by assumption $m$ (ans also $2N+m$) did not occur in the old sequence. And condition 2 is satisfied as well because $|a_{2n+2}-a_{2n+1}|=2N>N$, $|a_{2n+1}-a_{2n}|\ge N+m>N$, and $|a_{2n+2}-a_{2n+1}|=a_{2n+1}-m\ne a_{2n+1}-a_{2n}=|a_{2n+1}-a_{2n}|$.
• Finally, if $T_{n+1}$ asks to include $m$ as difference, let $a_{2n+1}=2N+m$, $a_{2n+2}=2N$. Again, the conditions are readily verified.

In each case, we obtain an extended suitable sequence. $_\square$

By repeatedly applying the claim (starting from the empty sequence), we recursivle obtain an infinite sequence $(a_n)_{n\in\mathbb N}$ such that each finite prefix of even length is suitable. Then

• $a_i\ne a_j$ for $1\le i<j$
• $|a_{i+1}-a_i|\ne |a_{j+1}-a_j|$ for $1\le i<j$
• For each task $T_k$ there is an index $i\le 2k$ where $T_k$ is fulfilled.

We conclude that $n\mapsto a_n$ and $n\mapsto |a_{n+1}-a_n|$ are bijections, as intended.

• In the first part of the argument, it is not clear to me that $\Phi(\mathbb b)$ is lexically before $\Phi(\mathbb a)$. Sure enough we have $b_{r+1}<a_{r+1}$, but just before that in the $\Phi$ sequence we have $|b_{r+1}-b_r| > |a_{r+1}-a_r|$ (since $b_r=a_r>m$), which is the wrong way! – Henning Makholm Nov 16 '14 at 2:42
• On the other hand, the argument could probably be salvaged if we take something like $$\Phi(\mathbb a)=(a_2,a_1,|a_4-a_3|,a_3,a_4,a_6,a_5,\ldots a_{4n+2},a_{4n+1},|a_{4n+4}-a_{4n+3}|,a_{4n+3},a_{4n+4},\ldots)$$ where in the lexicographically first sequence the $a_{4n+2}$s will be chosen for their absolute size and the $a_{4n+3}$s and $a_{4n+4}$s for the size of the jump between them. – Henning Makholm Nov 16 '14 at 3:01
• Ah yes, I edited $\Phi$ mid-argument. Have to rethink – Hagen von Eitzen Nov 16 '14 at 7:26
• @HenningMakholm It seems that even with your fix or similar reorderings it is hard to make sure that one does not run into a "dead end". I rewrote completely – Hagen von Eitzen Nov 16 '14 at 11:37