Estonian Math Competitions

The claim obviously holds for $n=1$, whence assume in the following that $n\ge 2$. Let $k$ be the minimal number of occurrences of a non-zero digit in the tuple $(d_0,d_1,\dots ,d_{n-1})$. Then the total number of occurrences of digits $5$, $6$, $7$, $8$, $9$ is at least $5k$. As each digit $5$, $6$, $7$, $8$, $9$ that is not the last digit of the tuple is followed by a digit $1$, and also $d_0=1$, the number of occurrences of digit $1$ is at least $5k$. Each digit $1$ that is not the last digit of the tuple is followed by either $2$ or $3$. Thus if the last digit is not $1$ then the total number of occurrences of $2$ and $3$ is at least $5k$. But if the last digit of the tuple is $1$ then the first $1$ of the tuple was previously not counted, whence the total number of occurrences of digits $2$ and $3$ is at least $5k$ in this case, too. Therefore, the number of occurrences of the only digit not counted yet, the digit $4$, is at most $n-15k$. As each occurrence of $8$ or $9$ follows a digit $4$, the total number of occurrences of $8$ and $9$ is also at most $n-15k$. Hence $n-15k\ge 2k$, implying $k\le \frac{n}{17}$.

To prove that $k<\frac{n}{17}$, suppose that $k=\frac{n}{17}$, i.e., $n=17k$. This implies that, in the argument above, every inequality must hold as an equality, i.e., each of the digits $5$, $6$, $7$, $8$, $9$ occurs exactly $k$ times and the digit $1$ occurs exactly $5k$ times. As $d_3=d_{13}=d_{23}=8$, the digit $8$ occurs more than once in the tuple $(d_0,d_1,\dots ,d_{17-1})$ and more than twice in the tuple $(d_0,d_1,\dots ,d_{2\cdot 17-1})$. Hence $k\ge 3$.

We show that each segment consisting of exactly $17$ consecutive terms of the tuple contains at least $5$ occurrences of the digit $1$. Indeed, the last term of the tuple $(2^i,2^{i+1},\dots ,2^{i+16})$ is exactly $65536$ times the first term, whence the last term contains at least $4$ more digits than the first term. As the first power of $2$ containing a certain number of digits definitely starts with $1$, the tuple $(2^{i+1},\dots ,2^{i+16})$ contains at least $4$ terms starting with $1$. If also $2^i$ starts with $1$ then there are at least $5$ such terms altogether; but if $2^i$ starts with a larger digit then the last term contains at least $5$ more digits than $2^i$, implying that there are still $5$ terms that start with $1$.

It remains to notice that the tuple $(d_0,d_1,\dots ,d_{3\cdot 17-1})$ contains the digit $1$ at least $16$ times because $d_0=1$ and $2^{3\cdot 17-1}=2^{50}=(2^{1024}{)}^5>(10^3{)}^5=10^{15}$, implying that the number $2^{3\cdot 17-1}$ has at least $16$ digits. As every segment $(d_{17i},d_{17i+1},\dots ,d_{17(i+1)-1})$ contains the digit $1$ at least $5$ times, the digit $1$ occurs in the tuple $(d_0,d_1,\dots ,d_{17k-1})$ more than $5k$ times. The contradiction shows that $k<\frac{n}{17}$.