Arranging numbers problem (induction)

  • Thread starter Thread starter issacnewton
  • Start date Start date
  • Tags Tags
    Induction Numbers
issacnewton
Messages
1,035
Reaction score
37
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: n=2

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

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

Now I am negating the goal and seeking the contradiction.
So assume that with any configuration of these n+1
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 n numbers, there is a configuration
such that for any pair of numbers, their average is not between them.
So let's put these n numbers in that particular
configuration. And now put n+1 at the end of this
list. But due to our assumption, for the list of all these
numbers (including n+1), there is no desired
configuration possible. So there must exist a number
1\leqslant i < n such that the average of i
and n+1 is between these two numbers. That average
is

\frac{n+1+i}{2}

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 don't know how to use it, so I started with another approach.Thanks
 
Physics news on Phys.org
I think that you have to come up with a scheme for the arrangement.
 
Sammy , can you give some hints for this arrangement ?
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...

Similar threads

Back
Top