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

Question

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?

Answer 1

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!

Answer 2

(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.