Splitting a Sum of Integers into Two Equal SumsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/