Adds up to a Thousand
Posted by Karl Sharman on January 6, 2011 – 3:34 pm
There are 3 different pairs of positive integers that add up to make 6:-
1+5=6
2+4=6
3+3=6
So how many different pairs of positive integers are there to make up 1,000?
As that is too easy, part 2 of the question…. How many different triplets of positive integers add up to make 1,000, and of course, how many different quads of positive integers?
January 6th, 2011 at 4:41 pm
500 unique pairs
83000 unique triples
January 6th, 2011 at 4:48 pm
For pairs, 1000/2 = 500
For each number in the range 1 to 1000 you can make 999 pairs, so 999,000/2 triplets. Each will be triplicated, so divide by 3 to get 166,500 triplets.
For each of the 500 pairs you can make 998/2 = 499 quads. Each pair will have a duplicate pair in the other set, so the answer is 500*499/2 = 124,750.
These answers off the top of my head, so probably wrong.
January 6th, 2011 at 5:23 pm
500 pairs
83,333 triples
6,965,278 quadruples
January 7th, 2011 at 8:23 am
but by what logic and formula do you get the triplets and quads?
January 7th, 2011 at 11:17 am
J cazayoux, if nobody posts the method, I’ll do it tonight. But that’ll be at least 5 hours from now.
January 8th, 2011 at 4:34 am
Aaaah!
I started off this post having worked out that I agreed with Nathan (i.e. triples – 83,333 unique combinations), now I’ve talked myself out of that based on the following……
If the three numbers making up the total of 1000 were labelled A, B & C then to ensure that every comination is unique A can only have a range of 1-333, just as it has a range of 1-500 for the pairs.
That leaves us needing to calculate the combinations of B & C, the 2 remaining numbers, for each of the 333 values of A.
When A=1, B+C = 999 with 2 digits selected from the range 1 to 998, this gives 499 unique combinations.
When A=2, B+C = 998 with 2 digits selected from the range 2 to 996 (if A=2 then neither B or C can be 1 as this would cause a repeated combination which matches one of those when A=1), this gives 497 unique combinations.
When A=3, B+C = 997 with 2 digits selected from the range 3 to 994 (as above we cannot use numbers 1 or 2 for values of B or C as this would cause a repeated combination), this gives 496 unique combinations.
When A=4, B+C = 996 with 2 digits selected from the range 4 to 992, this gives 494 unique combinations.
When A=5, B+C = 995 with 2 digits selected from the range 5 to 990, this gives 492 unique combinations.
So a pattern emerges with the number of combinations for B&C reducing by 3 between each subsequent odd / even value of A.
At that stage my maths knowledge wasn’t enough to express that as a formula so I used a spreadsheet to calculate by brute force. No doubt someone on here can provide a much neater mathematical representation.
So, after all that, my answer is 83,167.
January 8th, 2011 at 4:36 am
Amendment – when A=5 there are 493 unique combinations of B and C
January 19th, 2011 at 1:51 pm
Sorry Dual Aspect, I haven’t posted an answer. I do not have a definitive answer, although my calculations agree with Nathan,post 3.
January 19th, 2011 at 2:24 pm
Hi Karl,
That’s ok, I thought you would agree with Nathan’s answer, I started off in agreement with it too but changed my mind as I was composing the post with my reasoning.
I’m still uncertain which is right, but my spreadsheet from which I gained my answer seems to provie a neat solution with the number of combinations reducing to just 2 alternatives when A=332 and then just 1 combination when A=333, which is exactly what I would expect it to do.
So I can’t see the flaw in my calculations, yet I want to believe that it’s 83,333 as it seems like a “nicer” number which sounds more plausible than my 83,167.
Perhaps Chris can clarify??
August 23rd, 2012 at 4:13 am
I realise this was a while ago, but I can confirm that the correct answer is 83,333. My method was:
Think of 1000 dots in a row. We can partition these into 3 groups by placing 2 ‘barriers’ in the gaps between dots (there will be 999 of these). If you count the number of dots in each section you get 3 numbers that sum to 1000, and all possible choices of ‘barriers’ give all possible ways (999 choose 2 = 498,501).
But of course this counts every ordering of the numbers as unique, whereas we don’t want to consider the order they are summed in. There are 3!=6 ways to rearrange 3 different numbers so we want to divide by 6. However, some combinations have repeated numbers e.g. 1+1+998 so there are only 3 ways to reorder these (998+1+1 and 1+998+998), so we need to add a ‘duplicate’ for each of these possibilities (i.e. 3 extra for each triple with a repeated number) so when we divide by 6 we get the correct number. There are 499 triples where a duplicate is possible: (1,1,998), (2,2,996),…,(499,499,2). Hence we add 499*3 before dividing by 6 (note that there are no possibilities where all 3 numbers are the same so we do not have to consider the effect of this).
Hence, number of possibilities is (498,501 + (499*3))/6 = 83,333.
It took me a while to work out the error in Dual Aspect’s post. In fact, the method is completely sound (to find a formula for the number of combinations instead of brute force, look up ’sum of arithmetic series’: the 167 odd terms are given by 3n-2 for integers n between 1 and 167; their sum is given by (499+1)*167/2).
The problem lies in a simple counting error for the even values of A; each one has been underestimated by 1. So for A=2 there are 498 possibilities, A=4 has 495 etc. This is because there are as many pairs that sum to 998 as there are to 999 (in general, n and n+1) since you have 499+499=998 and 499+500=999 but not 499.5+499.5.
Hope this helps.