HMMT 十一月 2019 · 冲刺赛 · 第 22 题

HMMT November 2019 — Guts Round — Problem 22

[12] Let f ( n ) be the number of distinct digits of n when written in base 10. Compute the sum of f ( n ) as n ranges over all positive 2019-digit integers.

解析

[12] Let f ( n ) be the number of distinct digits of n when written in base 10. Compute the sum of f ( n ) as n ranges over all positive 2019-digit integers. Proposed by: Milan Haiman ( ) 2019 2019 Answer: 9 10 − 9 Write f ( n ) = f ( n ) + · · · + f ( n ) , 0 9 where f ( n ) = 1 if n contains the digit d and 0 otherwise. The sum of f ( n ) over all 2019-digit positive d d integers n is just the number of 2019-digit positive integers that contain the digit d . For 1 ≤ d ≤ 9, ∑ 2018 2018 f ( n ) = 9 · 10 − 8 · 9 . d n Also, ∑ 2018 2019 f ( n ) = 9 · 10 − 9 . 0 n Summing over all possible values of d , we compute 9 ∑ ∑ ∑ ( ) 2018 2018 2018 2019 2019 2019 f ( n ) = f ( n ) = 9(9 · 10 − 8 · 9 ) + 9 · 10 − 9 = 9 10 − 9 . d n n d =0