Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 14 down vote accepted

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.

share|improve this answer
    
+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

Your Answer

 
discard

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.