1. Limited time only! Sign up for a free 30min personal 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!

Arranging numbers problem (induction)

  1. Oct 15, 2011 #1
    hi

    Here is a problem I am trying to do ..

    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.

    Here is my attempt. The base case will consist of first two numbers.
    So

    Base Case: [tex]n=2[/tex]

    The arrangment 1,2 doesn't have average of 1 and 2 between them.
    So this proves [tex]P(2)[/tex]

    Induction case: Let [tex]n\geqslant 2[/tex] be arbitrary.
    Suppose [tex]P(n)[/tex]. To prove [tex]P(n+1)[/tex],
    consider numbers [tex]1,2,\cdots,n,n+1[/tex]

    Now I am negating the goal and seeking the contradiction.
    So assume that with any configuration of these [tex]n+1[/tex]
    numbers, there always is at least a pair of numbers such that
    their average is between them. Now due to the inductive hypothesis,
    we know that for first [tex]n[/tex] numbers, there is a configuration
    such that for any pair of numbers, their average is not between them.
    So lets put these [tex]n[/tex] numbers in that particular
    configuration. And now put [tex]n+1[/tex] at the end of this
    list. But due to our assumption, for the list of all these
    numbers (including [tex]n+1[/tex]), there is no desired
    configuration possible. So there must exist a number
    [tex]1\leqslant i < n [/tex] such that the average of [tex]i[/tex]
    and [tex]n+1[/tex] is between these two numbers. That average
    is

    [tex]\frac{n+1+i}{2}[/tex]

    Now after this point I don't know how to seek the contradiction.
    Any hints will be helpful. There is one hint given in the problem.

    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.

    But I dont know how to use it, so I started with another approach.


    Thanks
     
  2. jcsd
  3. Oct 15, 2011 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I think that you have to come up with a scheme for the arrangement.
     
  4. Oct 15, 2011 #3
    Sammy , can you give some hints for this arrangement ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Arranging numbers problem (induction)
  1. Arrangement problem (Replies: 3)

  2. Induction problem (Replies: 1)

  3. Problem on induction (Replies: 2)

Loading...