1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction problem

  1. Dec 30, 2011 #1
    1. The problem statement, all variables and given/known data
    Show that it is possible to arrange the numbers 1, 2, ... n in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices 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.]

    2. Relevant equations

    3. The attempt at a solution
    I'm using the following scheme to arrange the numbers: everytime a new number (n) is added to the list, I first put it at the end of the list. Then, I look for a previous number (m) to see whether (n+m)/2 is between n and m; if it is, then I put n before (n+m)/2.

    For n = 2:
    1, 2
    For n = 3:
    (3 + 1)/2 = 2; therefore, I put 3 before 2:
    1, 3, 2
    For n = 4:
    4 can be put in the end of the list.
    1, 3, 2, 4
    For n = 5:
    (5 + 1)/2 = 3; therefore, I put 5 before 3.
    1, 5, 3, 2, 4
    For n = 6: 1, 5, 3, 2, 6, 4
    For n = 7: 1, 5, 3, 2, 7, 6, 4
    For n = 8: 1, 5, 3, 2, 7, 6, 4, 8
    For n = 9: 1, 9, 5, 3, 2, 7, 6, 4, 8
    For n = 10: 1, 9, 5, 3, 2, 7, 10, 6, 4, 8
    And so on.

    I don't see any useful patterns here. I'm not sure why it only has to be proven when n is a power of two. The only pattern I see here is that the greatest power of two can always be put at the end of the list (in this case, until n = 3, 2 is at the end of the list; from n = 4 to n = 7, 4 is at the end of the list; starting from n = 8, 8 remains at the end of the list; and so on), but I don't know if this is helpful.
    Any ideas?

    Thank you in advance.
     
  2. jcsd
  3. Dec 30, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If you have n numbers then there is a k such that 2^k is greater then n. Remove the numbers you don't need from the list of 2^k numbers. And I do see a trend in your lists, the odd numbers and the even numbers are tending to fall into two different groups. Can you think of a way to order the evens and odds separately to do the induction?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook