Maths Olympiad Prep

Library / /21 of 100

Combinatorics Difficulty 4.3 AIME Find the answer China

The number of positive integer solutions of equation x+y+z=2010x + y + z = 2010 with xyzx \le y \le z is ________.

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

Solution

It is easy to find that the number of positive integer solutions of x+y+z=2010x + y + z = 2010 is C20092=2009×1004C_{2009}^2 = 2009 \times 1004.
We now classify these solutions into three categories:

(1)
x=y=zx = y = z, the number in this category is obviously 1;

(2) there are exactly two that are equal among x,y,zx, y, z
the number in this category is 1003;

(3) x,y,zx, y, z are different from each other — suppose the number in this category is kk.
From
1+3×1003+6k=2009×1004, 1 + 3 \times 1003 + 6k = 2009 \times 1004,
we have
6k=2009×10043×10031=2006×10052009+3×21=2006×10052004. \begin{align*} 6k &= 2009 \times 1004 - 3 \times 1003 - 1 \\ &= 2006 \times 1005 - 2009 + 3 \times 2 - 1 \\ &= 2006 \times 1005 - 2004. \end{align*}
We get k=1003×335334=335671k = 1003 \times 335 - 334 = 335671.
Therefore, the number of positive integer solutions
satisfying xyzx \le y \le z is
1+1003+335671=336675. 1 + 1003 + 335671 = 336675.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.