Maths Olympiad Prep

Library / /9 of 62

, 2020

Combinatorics Difficulty 4.2 AIME Find the answer United States

Problem:

Estimate AA, the number of times an 8-digit number appears in Pascal's triangle. An estimate of EE earns max(0,20AE/200)\max (0,\lfloor 20-|A-E| / 200\rfloor) points.

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

Solution

Solution:

We can obtain a good estimate by only counting terms of the form (a1)\binom{a}{1}, (a2)\binom{a}{2}, (aa1)\binom{a}{a-1}, and (aa2)\binom{a}{a-2}. The last two cases are symmetric to the first two, so we will only consider the first two and multiply by 2 at the end.

Since (a1)=a\binom{a}{1}=a, there are 90,000,000 values of aa for which (a1)\binom{a}{1} has eight digits. Moreover, since (a2)a2/2\binom{a}{2} \approx a^{2} / 2, the values of aa for which (a2)\binom{a}{2} has eight digits vary from about 2107\sqrt{2 \cdot 10^{7}} to 2108\sqrt{2 \cdot 10^{8}}, leading to about 1042(1101/2)140000.69=966010^{4} \sqrt{2}\left(1-10^{-1 / 2}\right) \approx 14000 \cdot 0.69=9660 values for aa.

Therefore, these terms yield an estimate of 180019320, good enough for 13 points. Of course, one would expect this to be an underestimate, and even rounding up to 180020000 would give 16 points.

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.