Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/