# Difficult mathematics induction proofing

1. Sep 4, 2008

### complicated

1. The problem statement, all variables and given/known data
my english isn't very well so i'll just write the question from my handbook

show that it is possible to arrange the number 1,2,3,...,n in a row so that the average of any two of this numbers never appears between them
[HINT : show that it is suffice to prove this fact when n is a power of 2.then use mathematical induction to prove the result when n is a power of 2]

3. The attempt at a solution
the question is

1.is there any connection between "n is power of 2" with a method to arrange that numbers?
cause i didn't see one..tell what u think

2.what i knew this far is the mathematical induction here is to prove that the statement "the numbers can be arranged that way" is true..so i think i must find some certain way like some formula to arrange it when the total number is n or n+1
and i don't find it so far..

note: the hint is true,because every question in my handbook have a hint

give me a hint or anything that u've discovered..tq

2. Sep 5, 2008

### morphism

Have you tried looking at small cases, e.g. n=2^2, 2^3 or 2^4?

My hint for you is to consider even and odd numbers. (In particular, the average of two numbers of different parity, i.e. an odd number and an even number, isn't an integer.)

3. Sep 5, 2008

### alphachapmtl

If n=2^0 or 2^1, it is trivially true.

If true for n=2^m,
with sequence a(1), a(2), .., a(2^m+1).
Then true for n=2^(m+1),
with sequence 2a(1)-1, 2a(2)-1, .., 2a(2^m+1)-1, 2a(1), 2a(2), .., 2a(2^m+1).

If true for n=4,
with sequence 1, 3, 2, 4.
Then true for n=8,
with sequence 1, 5, 3, 7, 2, 6, 4, 8.

so 1,2
to 1,3,2,4
to 1,5,3,7,2,6,4,8
to 1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16
to ...
is one sequence possible (not the only one).

4. Sep 6, 2008

### complicated

wow..

thank you..so far i only think how the numbers can have the same way to arranged
and that makes me forget what the true question is,,to prove that its a possible sequence!!..

thank you sooooo much!!! ^^