Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 SSMO Tiebreaker Round Problems/Problem 3"

(Created page with "==Problem== Let <math>A=\dots a_2a_1a_0.a_{-1}a_{-2}a_{-3}\dots</math> be a terminating decimal. The length of <math>A</math> is defined to be the length of the shortest sub-...")
 
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
\sol 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*}
 +
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}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c}
 +
  & 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 <math>\frac{11}{10},</math> we have
 +
 +
\begin{array}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c}
 +
  & 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 <cmath>5.5+0.5+0.045 = 6.045.</cmath> Combining, we can approximate the expression as <cmath>6790123456.05-6.045-1.05=6790123448.955\implies</cmath><cmath>\left\lfloor6790123448.955\right\rfloor = \boxed{6790123448}.</cmath>
 +
 +
~SMO_Team

Revision as of 14:49, 10 September 2025

Problem

Let $A=\dots a_2a_1a_0.a_{-1}a_{-2}a_{-3}\dots$ be a terminating decimal. The length of $A$ is defined to be the length of the shortest sub-sequence of consecutive digits that include all nonzero digits and at least one of $a_0,a_{-1}.$ So, the length of $12.03$ is $4$ and the length of $0.123$ is $3.$ Let $f(n)$ be the average of all numbers with a terminating decimal of length $n.$ Find the value of $\left\lfloor\sum_{n=0}^{10}(n+1)f(n)\right\rfloor.$

Solution

\sol First, we will compute the value of $f(n).$ Denote $f(n,k)$ as the expected value of a terminating decimal of length $n$ with leading term $a_k.$ 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).\] So, \[\sum_{n=0}^{10}(n+1)f(n)=\sum_{n=0}^{10}\sum_{i=-1}^{n-1}f(n,i).\] 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}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c} 

 & 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 $\frac{11}{10},$ we have

\begin{array}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c} 

 & 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.\] Combining, we can approximate the expression as \[6790123456.05-6.045-1.05=6790123448.955\implies\]\[\left\lfloor6790123448.955\right\rfloor = \boxed{6790123448}.\]

~SMO_Team

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_SSMO_Tiebreaker_Round_Problems/Problem_3&oldid=260299"