Maths Olympiad Prep

Library / /31 of 62

, 2020

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:
The number 30033003 is the only number known to appear eight times in Pascal's triangle, at positions
(30031),(30033002),(a2),(aa2),(15b),(1515b),(146),(148) \binom{3003}{1},\binom{3003}{3002},\binom{a}{2},\binom{a}{a-2},\binom{15}{b},\binom{15}{15-b},\binom{14}{6},\binom{14}{8}
Compute a+b(15b)a+b(15-b).

Solution

Solution:
We first solve for aa. Note that 3003=3711133003=3 \cdot 7 \cdot 11 \cdot 13. We have 3003=(a2)=a(a1)2a223003=\binom{a}{2}=\frac{a(a-1)}{2} \approx \frac{a^{2}}{2}. This means we can estimate a30032a \approx \sqrt{3003 \cdot 2}, so aa is a little less than 8080. Furthermore, 1123003=a(a1)11 \mid 2 \cdot 3003=a(a-1), meaning one of aa or a1a-1 must be divisible by 1111. Thus, either a=77a=77 or a=78a=78. Conveniently, 137813 \mid 78, so we get a=78a=78 and we can verify that (782)=3003\binom{78}{2}=3003.

We solve for b<15bb<15-b satisfying (15b)=3003\binom{15}{b}=3003. Because (15b)=15!b!(15b)!\binom{15}{b}=\frac{15!}{b!(15-b)!} is divisible by 1111, we must have b5b \geq 5. But we're given (146)=3003\binom{14}{6}=3003, so b<6b<6. We conclude that b=5b=5, and it follows that a+b(15b)=128a+b(15-b)=128.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.