Inductive Construction

Posted on January 27, 2015 by Sumant Sumant

Given n numbers is it possible to arrange the numbers in a row so that the arithmetic mean of any two of these numbers is not equal to some number between them?

Let’s begin with two numbers 1,2

Three numbers 1,3,2 or 2,3,1  or 3,1,2

Similarly for four numbers it is 2,4,1,3. It’s easy to see that if we keep evens together and odds together then we have a fair chance of keeping them separate.

Let a_1,a_2,...,a_{2^k} is a possible sequence of arranging the numbers 1,2,...2^k . Consider the sequences 2a_1,2a_2,...,2a_{2^k} and 2a_1-1,2a_2-1,2a_{2k}-1 is a permutation of 2^{k+1}. The first one is sequence of all even numbers and the second one is sequence of all odd numbers.

As a_1,a_2,...,a_{2^k} is already arranged by induction hypothesis. Our claim is that 2a_1,2a_2,...,2a_{2^k} is also arranged and so is 2a_1-1,2a_2-1,...,2a_{2^k}-1

About Sumant Sumant

I love Math and I am always looking forward to collaborate with fellow learners. If you need help learning math then please do contact me.
This entry was posted in Mathematical Induction, Number Theory, Sequences and tagged . Bookmark the permalink.

Leave a comment