Maths Olympiad Prep

Library / HMMT February /536 of 1302

HMMT February

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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 A≤B≤CA \leq B \leq C. Then AA can range from 1 to 667, inclusive. For odd AA, there are 1000−3(A−1)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 1002−3A21002-\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.