# Arrangement of Numbers

How can we prove that it is posible to arrange numbers $1,2,3,4,\ldots, n$ in a row so that the average of any two of these numbers never appears between them?

-

## 1 Answer

Assume the inductive hypothesis that it is true for lists smaller than n. To reorder 1...n this way as well, split it into evens and odds, and apply the function floor((x+1)/2) to these sets to create two half-problems of the same type which by the hypothesis can be solved. Now unapply the transformation to each half-solution using the function 2x to recover the evens and the function 2x-1 to recover the odds. These functions are linear so the condition is still satisfied. Now concatenate these two lists together to form the solution. This concatenation always works because the average of an even and an odd is not an integer.

-
+1. This is much simpler than mine. –  Aryabhata Aug 23 '10 at 18:56
Very well put. I'd only like to point out that the floor((x+1)/2) gives n when x=2n or when x=2n-1, which is why the latter functions recover the evens and the odds. –  Vladimir Sotirov Aug 23 '10 at 19:14