Difference between revisions of "2024 SSMO Tiebreaker Round Problems/Problem 3"
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| − | + | First, we will compute the value of <math>f(n).</math> Denote <math>f(n,k)</math> as the expected value of a terminating decimal of length <math>n</math> with leading term <math>a_k.</math> We have <cmath>f(n) = \frac{\sum_{i=-1}^{n-1}f(n,i)}{n+1}\implies f(n) = \sum_{i=-1}^{n-1}f(n,i).</cmath> So, <cmath>\sum_{n=0}^{10}(n+1)f(n)=\sum_{n=0}^{10}\sum_{i=-1}^{n-1}f(n,i).</cmath> Now, | |
\begin{align*} | \begin{align*} | ||
f(n,i)&=\mathbb{E}\left(a_ia_{i-1}\dots a_0.a_{-1}\dots a_{i+1-n}\right)\\ | f(n,i)&=\mathbb{E}\left(a_ia_{i-1}\dots a_0.a_{-1}\dots a_{i+1-n}\right)\\ | ||
| Line 26: | Line 26: | ||
Now, we will approximate this value. The first summation approximates to | Now, we will approximate this value. The first summation approximates to | ||
| + | \[ | ||
\begin{array}{ccccccccccccc} | \begin{array}{ccccccccccccc} | ||
& 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ | & 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & . & 0 \\ | ||
| Line 36: | Line 37: | ||
& & & & & & & 4 & 0 & 0 & 0 & . & 0 \\ | & & & & & & & 4 & 0 & 0 & 0 & . & 0 \\ | ||
& & & & & & & & 4 & 5 & 0 & . & 0 \\ | & & & & & & & & 4 & 5 & 0 & . & 0 \\ | ||
| − | + | + | + & & & & & & & & & 5 & 0 & . & 0 \\ |
\hline | \hline | ||
& 6 & 1 & 7 & 2 & 8 & 3 & 9 & 5 & 0 & 5 & . & 5 \\ | & 6 & 1 & 7 & 2 & 8 & 3 & 9 & 5 & 0 & 5 & . & 5 \\ | ||
\end{array} | \end{array} | ||
| + | \] | ||
Multiplying by <math>\frac{11}{10},</math> we have | Multiplying by <math>\frac{11}{10},</math> we have | ||
Revision as of 14:51, 10 September 2025
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 ![\[f(n) = \frac{\sum_{i=-1}^{n-1}f(n,i)}{n+1}\implies f(n) = \sum_{i=-1}^{n-1}f(n,i).\]](http://latex.artofproblemsolving.com/e/5/3/e5345355429017c8f345ccc1eba249f3165068bc.png)
So, ![\[\sum_{n=0}^{10}(n+1)f(n)=\sum_{n=0}^{10}\sum_{i=-1}^{n-1}f(n,i).\]](http://latex.artofproblemsolving.com/d/4/c/d4c6a48f3cf22d4ffcbe8dfeb178ee5293a91fe7.png)
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 ![\[5.5+0.5+0.045 = 6.045.\]](http://latex.artofproblemsolving.com/c/f/2/cf2568f108bfe412b375424065adcff9286670d2.png)
Combining, we can approximate the expression as ![\[6790123456.05-6.045-1.05=6790123448.955\implies\]](http://latex.artofproblemsolving.com/9/1/1/9116f53dfef63131a564a2ab1ad0bcf2aeb568fd.png)
![\[\left\lfloor6790123448.955\right\rfloor = \boxed{6790123448}.\]](http://latex.artofproblemsolving.com/9/3/f/93f1191710d4e6b1d65ffb048831e1c9f7e52972.png)
~SMO_Team
