2024 SSMO Tiebreaker Round Problems/Problem 3

Problem

Let be a terminating decimal. The length of is defined to be the length of the shortest sub-sequence of consecutive digits that include all nonzero digits and at least one of So, the length of is and the length of is Let be the average of all numbers with a terminating decimal of length Find the value of

Solution

First, we will compute the value of Denote as the expected value of a terminating decimal of length with leading term We have So, Now, \begin{align*} f(n,i)&=\mathbb{E}\left(a_ia_{i-1}\dots a_0.a_{-1}\dots a_{i+1-n}\right)\\ &=\mathbb{E}\left(\sum_{k=i+1-n}^{i}a_k10^k\right)\\ &=\sum_{k=i+1-n}^i\mathbb{E}\left(a_k10^k\right)\\ &=\sum_{k=i+1-n}^i10^k\mathbb{E}\left(a_k\right)\\ &=10^i\mathbb{E}(a_i)+\sum_{k=i+1-n}^{i-1}10^k\mathbb{E}\left(a_k\right)\\ &=10^i\left(\frac{\sum_{k=1}^{9}k}{9}\right)+\sum_{k=i+1-n}^{i-1}10^k\mathbb{E}\left(\frac{\sum_{k=0}^{9}k}{10}\right)\\ &=5\cdot10^i+\sum_{k=i+1-n}^{i-1}\left(4.5\cdot10^k\right). \end{align*} Substituting, we have \begin{align*} \sum_{n=1}^{10}(n+1)f(n)&=\sum_{n=1}^{10}\sum_{i=-1}^{n-1}f(n,i)\\ &=\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\left(5\cdot10^i+\sum_{k=i+1-n}^{i-1}\left(4.5\cdot10^k\right)\right)\\ &=\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\left(5\cdot10^i\right)+\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\sum_{k=i+1-n}^{i-1}\left(4.5\cdot10^k\right)\\ &=\left(\sum_{i=-1}^{9}\left((50-5i)\cdot10^i\right)-\frac{1}{2}\right)+\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\left(4.5\cdot\left(\frac{10^{i}-10^{i+1-n}}{9}\right)\right)\\ &=\left(\sum_{i=-1}^{9}\left((50-5i)\cdot10^i\right)-\frac{1}{2}\right)+\frac{1}{10}\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\left(5\cdot10^i\right)-\sum_{n=1}^{10}\sum_{i=-1}^{n-1}\left(\frac{10^{i+1-n}}{2}\right)\\ &=\left(\sum_{i=-1}^{9}\left((50-5i)\cdot10^i\right)-\frac{1}{2}\right)+\frac{1}{10}\left(\sum_{i=-1}^{9}\left((50-5i)\cdot10^i\right)-\frac{1}{2}\right)\\&-\left(\sum_{i=-10}^{0}\left(\frac{(i+11)\cdot10^{i}}{2}\right)+\frac{1}{2}\right)\\ &=\frac{11}{10}\left(\sum_{i=-1}^{9}\left((50-5i)\cdot10^i\right)\right)-\sum_{i=-10}^{0}\left(\frac{(i+11)\cdot10^{i}}{2}\right)-\frac{21}{20}.\\ \end{align*} Now, we will approximate this value. The first summation approximates to

\begin{array}{ccccccccccccc} & & 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & & 1 & 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & & & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & & & & 2 & 5 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & & & & & 3 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ & & & & & & & 3 & 5 & 0 & 0 & 0 & . & 0 \\ & & & & & & & & 4 & 0 & 0 & 0 & . & 0 \\ & & & & & & & & & 4 & 5 & 0 & . & 0 \\ & + & & & & & & & & & 5 & 0 & . & 0 \\ \hline & & 6 & 1 & 7 & 2 & 8 & 3 & 9 & 5 & 0 & 5 & . & 5 \\ \end{array}

Multiplying by we have

\begin{array}{cccccccccccccc} & & 6 & 1 & 7 & 2 & 8 & 3 & 9 & 5 & 0 & 5 & . & 5 & 0 \\ &+ & 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & . & 0 & 5 \\ \hline & & 6 & 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & . & 0 & 5 \\ \end{array}

Now, the second summation is approximately Combining, we can approximate the expression as

~SMO_Team