Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can we rearrange the integers, such that the arithmetic average of any two numbers does not appear between them?

In other words: Can we have a sequence $\{a_n\}_{n\in \mathbb{Z}}$, where all integers appear once and only once, such that $a_j\ne (a_i+a_k)/2,\forall i<j<k$?

I've noticed the questions here and here. But the first one only applies to arbitrarily long finite segments. The second does not contain a solution in itself, and unfortunately I can not access the reference (for free).

Also, the second question is much more general than this one, so I am wondering if this one can be solved somewhat more easily.

share|cite|improve this question
As you noticed, the paper contains the assertion that there is no such ordering. – André Nicolas Jul 4 '13 at 4:22
? When I looked at the second link, the existence of such "chaotic orderings" of the integers is said to be known, and the authors (going for the same in reals) begin by constructing an explicit one for the integers. – coffeemath Jul 4 '13 at 5:57
I think this article: On permutations containing no long arithmetic progressions would be of interest to you (it happens that it is the second reference in the previously mentioned paper). – dtldarek Jul 4 '13 at 9:12
There seems to be a big difference between the question for $\mathbb{Z}$ versus only $\mathbb{N}$. The chaotic construction I came across following the second link was definitely for $\mathbb{Z}$ (chaotic: no average of two terms lies between them) – coffeemath Jul 4 '13 at 11:22
@dentisDark It seems that you should also add a condition that the range of the sequence $\{a_n\}$ is $\mathbb Z$, because the present formulation is not equivalent to the first and the reformulated question has an easy answer: for any injection $i:\mathbb Z\to\mathbb N$ and each $n\in\mathbb Z$ put $a_n=2^{i(n)}$. – Alex Ravsky Jul 5 '13 at 1:00
up vote 2 down vote accepted

Collecting references from the comments: The paper On permutations containing no long arithmetic progressions (by Davis, Entringer, Graham and Simmons in Acta Aritmetica 34(1), 1977) shows that this is not possible (Fact 5 on page 85).

Actually what is shown is that a doubly-infinite list of naturals can't have this property, but if you have a a doubly-infinite list of integers and delete the negative numbers, you either get that or a singly infinite list of naturals, for which it is easy to see that the property is impossible.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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