Splitting a Sum of Integers into Two Equal Sums

Date: 09/07/2004 at 13:33:40
From: Chris
Subject: Integers & Sum of Integers

My question relates to a classic Cuisenaire-rod problem.

Given n rods, all with different integer lengths (1,2,...,n), we must 
combine these into 2 rods of equal length.

Each of these rods must therefore have the length:

         sum(1 + 2 + 3 + ... + n)
    L =  ------------------------
                    2

From this we know that sum(1 + 2 + ... + n) MUST be an even number, in 
order for us to create 2 equally "long" rods.  (This is obvious, since
all rod lengths are integers and an odd number divided by 2 won't
produce an integer result.)

We also know that since every rod has a different length from 1 to n,
we can only use each integer once.

How do I prove that the 2 rods of same length (half the sum of all the
rod lengths) can be created, using ALL the integers only once?

Thank you for your time.

Chris

Date: 09/07/2004 at 16:23:40
From: Doctor Douglas
Subject: Re: Integers & Sum of Integers

Hi Chris.

Thanks for writing to the Math Forum.

First ask yourself what numbers N permit

  sum(N) 

to be divisible by 2?  As you suggested, we know that sum(N) must be
even in order for it to work.  Try listing them.  You should find that 
the permissible values of N are {3,4,7,8,11,12,...}.  Notice the
pattern in these numbers.  The partition can then be accomplished for
the first few values easily:

  3:   1 + 2 = 3
  4:   1 + 4 = 2 + 3
  7:   1 + 2 + 4 + 7 = 3 + 5 + 6
  8:   1 + 4 + 5 + 8 = 2 + 3 + 6 + 7

Then see if you can find a way to use an inductive proof so that if
you know that it is possible for some N = k, then it works for N = k +
4.  This is the hardest part of the proof that as long as sum(N) is 
divisible by 2, you can always make the partition of the N numbers 
into two sets, each of which has sum equal to sum(N)/2.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/08/2004 at 09:19:20
From: Chris
Subject: Thank you (Integers & Sum of Integers)

Thank you very much for your hint.  I think I've got it right now, and
the proof turned out to be much simpler than I'd imagined:

  Sum(n + 4) = (1+2+...+n) + (n+1) + (n+2) + (n+3) + (n+4)

For a given value of n, partition of sum(n) is possible, so the
partition of sum(n + 4) will be possible, if

   (n+1) + (n+2) + (n+3) + (n+4)

can be partitioned internally.

We then have:

     (n+1) + (n+4) = (n+2) + (n+3)
 <=>        2n + 5 = 2n + 5

which is true, so sum(n + 4) can also be partitioned.

Since we know n = 3 and n = 4 works, we get:

n = 3 true   =>    n = 7 true
n = 4 true   =>    n = 8 true

n = 7 true   =>    n = 11 true
n = 8 true   =>    n = 12 true

... and so on.

Date: 09/08/2004 at 12:35:26
From: Doctor Douglas
Subject: Re: Thank you (Integers & Sum of Integers)

Hi Chris.

Very well done. 

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/