## 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.

August 29th, 2013 at 2:41 pm

@ Dan what about sum = 27..does your method works??

March 18th, 2015 at 3:19 am

83,333

The code snippet below, count the numbers sequences with non-descending order.

For example:

1. {1, 1, 998}

2. {1, 2, 997}

…

499. {1, 499, 500}

500. {2, 2, 996}

…

83333. {333, 333, 334}

// Written in C#

int n = 1000;

int count = 0;

for (int i = 1; i 0)

{

count += temp;

}

}

Console.WriteLine(count);

July 18th, 2015 at 8:13 pm

Are you include triplets with repeated numbers like this 994 + 2 + 2 = 1000?

How many different triplets without repeated numbers whose sum is equal to one thousand are there?

February 2nd, 2016 at 3:03 pm

SO the answer would be 501 because if you do 1 + 999 2 + 998 3 + 997 and so fourth you would do it 500 times but you can’t forget about 0 + 1000 which makes your answer 501. Example: If u were trying to find how many pairs go into 10 you would do, 1+9 2+8 3+7 4+6 5+5 0+10 since there are no more to add your answer would be half of 10 plus 1 which is 6.