Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /138 of 395

Saudi Arabian Mathematical Competitions

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=23⋅1791432=2^{3} \cdot 179. The equation is equivalent to
x!y!(x−y)!=23⋅179 \frac{x!}{y!(x-y)!}=2^{3} \cdot 179
or y!(x−y)!⋅23⋅179=x!y!(x-y)! \cdot 2^{3} \cdot 179 = x!. It follows 179∣x!179 \mid x!, hence x≥179x \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 y≤⌊x2⌋y \leq \left\lfloor \frac{x}{2} \right\rfloor. Then
(x1)<(x2)<…<(x⌊x2⌋). \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 y≥2y \geq 2, then we have
(xy)≥(x2)=x(x−1)2≥179⋅(179−1)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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.