HMMT 十一月 2020 · 冲刺赛 · 第 35 题

HMMT November 2020 — Guts Round — Problem 35

[20] Estimate A , the number of times an 8-digit number appears in Pascal’s triangle. An estimate of E earns max(0 , b 20 − | A − E | / 200 c ) points.

解析

[20] Estimate A , the number of times an 8-digit number appears in Pascal’s triangle. An estimate of E earns max(0 , b 20 − | A − E | / 200 c ) points. Proposed by: Daniel Zhu Answer: 180020660 ( ) ( ) ( ) a a a Solution: We can obtain a good estimate by only counting terms of the form , , , and 1 2 a − 1 ( ) a . The last two cases are symmetric to the first two, so we will only consider the first two and a − 2 multiply by 2 at the end. ( ) ( ) ( ) a a a 2 Since = a , there are 90000000 values of a for which has eight digits. Moreover, since ≈ a / 2, 1 1 2 √ √ ( ) a 7 8 the values of a for which has eight digits vary from about 2 · 10 to 2 · 10 , leading to about 2 √ 4 − 1 / 2 10 2(1 − 10 ) ≈ 14000 · 0 . 69 = 9660 values for a . 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.