Maths Olympiad Prep

Library / /292 of 348

Number theory Difficulty 5.1 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Write f(n)=f0(n)++f9(n)f(n)=f_{0}(n)+\cdots+f_{9}(n) where fd(n)=1f_{d}(n)=1 if nn contains the digit dd and 0 otherwise. The sum of fd(n)f_{d}(n) over all 2019-digit positive integers nn is just the number of 2019-digit positive integers that contain the digit dd. For 1d91 \leq d \leq 9, nfd(n)=9102018892018\sum_{n} f_{d}(n)=9 \cdot 10^{2018}-8 \cdot 9^{2018} Also, nf0(n)=910201892019\sum_{n} f_{0}(n)=9 \cdot 10^{2018}-9^{2019} Summing over all possible values of dd, we compute nf(n)=d=09nfd(n)=9(9102018892018)+910201892019=9(10201992019)\sum_{n} f(n)=\sum_{d=0}^{9} \sum_{n} f_{d}(n)=9\left(9 \cdot 10^{2018}-8 \cdot 9^{2018}\right)+9 \cdot 10^{2018}-9^{2019}=9\left(10^{2019}-9^{2019}\right)

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.