Maths Olympiad Prep

Library / /461 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

How many ways, without taking order into consideration, can 2002 be expressed as the sum of 3 positive integers (for instance, 1000+1000+21000+1000+2 and 1000+2+10001000+2+1000 are considered to be the same way)?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Call the three numbers that sum to 2002A,B2002 A, B, and CC. In order to prevent redundancy, we will consider only cases where ABCA \leq B \leq C. Then AA can range from 1 to 667, inclusive. For odd AA, there are 10003(A1)21000-\frac{3(A-1)}{2} possible values for BB. For each choice of AA and BB, there can only be one possible CC, since the three numbers must add up to a fixed value. We can add up this arithmetic progression to find that there are 167167 possible combinations of A,B,CA, B, C, for odd AA. For each even AA, there are 10023A21002-\frac{3 A}{2} possible values for BB. Therefore, there are 166833 possible combinations for even AA. In total, this makes 334000 possibilities.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.