Maths Olympiad Prep

Library / /41 of 520

Combinatorics Difficulty 6.3 National olympiad Find the answer

In how many ways can the number 20002000 be written as a sum of three positive, not necessarily different integers? (Sums like 1+2+31 + 2 + 3 and 3+1+23 + 1 + 2 etc. are the same.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find the number of ways to write the number 20002000 as a sum of three positive integers a,b,ca, b, c such that abca \leq b \leq c, we can follow these steps:

1. Define the problem in terms of inequalities:
We need to find the number of solutions to the equation a+b+c=2000a + b + c = 2000 where a,b,cNa, b, c \in \mathbb{N}^* and abca \leq b \leq c.

2. **Determine the range for aa:**
Since abca \leq b \leq c, the smallest value aa can take is 11. The largest value aa can take is 20003=666\left\lfloor \frac{2000}{3} \right\rfloor = 666.

3. **Determine the range for bb given aa:**
For a given aa, bb must satisfy ab2000a2a \leq b \leq \frac{2000 - a}{2}. This is because bb must be at least aa and at most 2000a2\frac{2000 - a}{2} to ensure bcb \leq c.

4. **Calculate the number of possible values for bb:**
- The minimum value of bb is b1=ab_1 = a.
- The maximum value of bb is b2=2000a2b_2 = \left\lfloor \frac{2000 - a}{2} \right\rfloor.

5. **Count the number of possible values for bb:**
The number of possible values for bb for a given aa is Na=b2b1+1N_a = b_2 - b_1 + 1.

6. **Express NaN_a in terms of aa:**
- For aa even, let a=2ma = 2m:
Na=20002m22m+1=1000m2m+1=10013m N_a = \left\lfloor \frac{2000 - 2m}{2} \right\rfloor - 2m + 1 = 1000 - m - 2m + 1 = 1001 - 3m
- For aa odd, let a=2m1a = 2m - 1:
Na=2000(2m1)2(2m1)+1=1000m+12m+1=10023m N_a = \left\lfloor \frac{2000 - (2m - 1)}{2} \right\rfloor - (2m - 1) + 1 = 1000 - m + 1 - 2m + 1 = 1002 - 3m

7. **Sum the number of triplets for all possible values of aa:**
N=m=1333(10013m)+m=1333(10023m) N = \sum_{m=1}^{333} (1001 - 3m) + \sum_{m=1}^{333} (1002 - 3m)
N=m=1333(20036m) N = \sum_{m=1}^{333} (2003 - 6m)

8. Calculate the sum:
N=m=13332003m=13336m N = \sum_{m=1}^{333} 2003 - \sum_{m=1}^{333} 6m
N=333×20036m=1333m N = 333 \times 2003 - 6 \sum_{m=1}^{333} m
The sum of the first 333 natural numbers is:
m=1333m=333×3342=55506 \sum_{m=1}^{333} m = \frac{333 \times 334}{2} = 55506
Therefore:
N=333×20036×55506 N = 333 \times 2003 - 6 \times 55506
N=666999333036=333963 N = 666999 - 333036 = 333963

The final answer is 333963\boxed{333963}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.