[Solved]: Order a list of whole numbers so that no two numbers have the average of them sitting between them

Problem Detail: 

Given a whole number N..

Arrange 1 to N in a sequence such that no two numbers have their average sitting between them...

Note - If N=20.. average of 19 and 2 = 10.5 is not a whole number .. hence we do not need to worry about such numbers and their averages.. In other words, if average of two numbers is not a whole number.. we assume that their average does not exist in the list 1 to N..

Asked By : abipc

Answered By : Steven Stadnicki

Here's a simple recursive construction for the more restrictive version of the problem. First of all, note that the average of an odd number and an even number is never a whole number; if $a=2i-1$ and $b=2j$, then $\frac12(a+b)=i+j-1+\frac12$. This means that if we put the $\lceil N/2\rceil$ odd numbers $a_i$ first (in some as-yet-to-be-determined order) and then the $\lfloor N/2\rfloor$ even numbers $b_j$ (likewise, in some as-yet-to-be-determined order), then we can be guaranteed that the average of a $a_i$ and a $b_j$ can never be between them (because it'll never be a whole number), so we've split the problem into two subproblems: one for the set of odd numbers $a_i$ and one for the set of even numbers $b_j$.

But note now that if we have two odd numbers $a_m=2m-1$ and $a_n=2n-1$, then their average is $2\left(\frac{m+n}2\right)-1$, and so the subproblem of 'sorting' the $a_i$ correctly is exactly the same as sorting the numbers $c_i\in 1\ldots n$, where $c_i=\frac{a_i+1}{2}$ and $n=\lceil N/2\rceil$; a similar result holds true for the even numbers $b_j$. This means that we can keep applying the same procedure to both of these groups recursively. For instance, when $N=8$ this construction produces the ordering $15372648$. Note that if we subtract one from these values and look at the numbers $0\ldots(N-1)$, then this ordering is $04261537$; looking at the bit patterns for these numbers ($000, 100, 010, 110, 001, 101, 011, 111$) shows that they're just the bit patterns of the numbers $0\ldots 7$, reversed! This 'bit reversal' shuffle is used by Fast Fourier Transform (FFT) algorithms to correct the output ordering of their data (see, for instance, http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html ).

In fact, this construction shows that there are at least $O(2^{N/2})$ such orderings, since at each of the $N/2$ 'internal' nodes we can choose to either put the odd or the even numbers first without spoiling the result. These don't exhaust all of the orderings, though; for instance, we can exchange $2$ and $7$ in the constructed $N=8$ ordering to get the ordering $15327648$ which also clearly satisfies the constraint but can never be constructed by this procedure (since odd and even numbers are 'intermingled'). I don't know how many of the $N!$ orderings of $1\ldots N$ actually satisfy the problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13857