Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Difficult mathematics induction proofing

  1. Sep 4, 2008 #1
    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..:frown:

    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. jcsd
  3. Sep 5, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.)
  4. Sep 5, 2008 #3
    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).
  5. Sep 6, 2008 #4

    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!!! ^^
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook