All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Different Sums (Posted on 2004-07-22) Difficulty: 3 of 5
There are 40 ways to make sums of three distinct positive integers total 25. (1+2+22 is such a sum, but 1+12+12 and 1+2+3+19 are not.)

How many different ways can three distinct positive integers sum to 1000?

See The Solution Submitted by Brian Smith    
Rating: 3.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Human Approach | Comment 6 of 17 |

Without using a program, this is my approach :

For 3 numbers to equal 1000, 1 will be 1-500 and the other 2 will make up the rest, so you find the number of ways to make 1-999 with 2 numbers.

To make an odd number x with 2 numbers, the simplest way is to do (x+1)/2 + (x-1)/2, eg 999 = (999+1)/2 + (999-1)/2 = 500+499. This can be modified by adding one to the highest number and subtracting one from the lowest number, eg 501+498 = 999 also. The lowest number will reach one after (x-3)/2 has been subtracted, giving (x-1)/2 ways of making this number by adding 2 numbers together. For 501 to 999, one of the solutions using this method will be invalid as it would involve a repeated number (eg 999=1+998, but that would give 1+1+998=1000, which is not allowed). So the number of solutions for the 999 is 498, for 997 is 497, down to 501 giving 249 solutions. 499 down to 1 would give the same set of solutions, so are not counted.

This gives 249+250.....+498+499 solutions, using triangle number formula n(n+1)/2 this means we have (499*500)/2 - (248*249)/2 solutions. However, each number will have one solution the same as each other number, because eg for 501 you will have (4+497)+499=1000, and for 503 you will get (4+499)+497=1000. You have 249 odd number 501-999 so we need to subtract 1+2+3....+248+249, leaving (499*500)/2 - (248*249)/2 - (249*250)/2, a total of 62749 unique solutions so far.

Then we have the even number only solutions. Let x be an even number from 500-998, that is not a multiple of 4. To make x with 2 even numbers we do [(x/2)+1] + [(x/2)-1]. After these initial solutions we add 2 to the higher number, and subtract 2 from the lower number. This will give (x-2)/4 solutions, again with one invalid, meaning it is (x-6)/4. for 998 we get 248 solutions, down to 502 giving us 124. There are 125 number in this set, meaning we have 1+2...+124+125 repeated solutions. Therefore from this set of numbers we can get (248*249)/2 - (123*124)/2 - (125*126)/2 equals 30750 solutions.

Let x be an even number from 500-998, that is a multiple of 4. The first 2 values this time will be [(x/2)+2] + [(x/2)-2].  Using similar calculations to the last set, i get another 30750 solutions. However none of these will be unique as i just realised they will all be the same as the above lol.

So i have a total of 62749+30750=93499 solutions. Almost certainly wrong but you get the gist of the method, it's long complicated, lots of places i could have made mistakes, and probably not the best way to do it either. Apart from all that, it's brilliant =)


  Posted by Nick Williams on 2004-07-22 11:02:15
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information