Maths Olympiad Prep

Library / /62 of 120

Combinatorics Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Find all positive integers xx and yy such that
(xy)=1432 \binom{x}{y}=1432

Solution

We have 1432=231791432=2^{3} \cdot 179. The equation is equivalent to
x!y!(xy)!=23179 \frac{x!}{y!(x-y)!}=2^{3} \cdot 179
or y!(xy)!23179=x!y!(x-y)! \cdot 2^{3} \cdot 179 = x!. It follows 179x!179 \mid x!, hence x179x \geq 179.

It is clear that (x,y)=(1432,1),(1432,1431)(x, y) = (1432, 1), (1432, 1431) are solutions. We shall prove that there are no other solutions. Because of the symmetry of the binomial coefficients, we can assume that yx2y \leq \left\lfloor \frac{x}{2} \right\rfloor. Then
(x1)<(x2)<<(xx2). \binom{x}{1} < \binom{x}{2} < \ldots < \binom{x}{\left\lfloor \frac{x}{2} \right\rfloor}.
If y=1y=1, then we get x=1432x=1432. If y2y \geq 2, then we have
(xy)(x2)=x(x1)2179(1791)2>1432, \binom{x}{y} \geq \binom{x}{2} = \frac{x(x-1)}{2} \geq \frac{179 \cdot (179-1)}{2} > 1432,
not possible.

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.