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?

  • $\begingroup$ What if the difference $|m-a_{i+2}|$ has already been used? $\endgroup$ – Brian M. Scott Nov 15 '14 at 21:40
  • $\begingroup$ @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. $\endgroup$ – Dexter Nov 15 '14 at 21:44
  • $\begingroup$ 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? $\endgroup$ – Marc van Leeuwen Nov 15 '14 at 22:42
  • $\begingroup$ @MarcvanLeeuwen I meant $|a_i-a_{i+1}|$ all along. Thanks for alerting me to that. $\endgroup$ – 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.

  • $\begingroup$ 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! $\endgroup$ – Henning Makholm Nov 16 '14 at 2:42
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 16 '14 at 3:01
  • $\begingroup$ Ah yes, I edited $\Phi$ mid-argument. Have to rethink $\endgroup$ – Hagen von Eitzen Nov 16 '14 at 7:26
  • $\begingroup$ @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 $\endgroup$ – Hagen von Eitzen Nov 16 '14 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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