Let $f(x)$ be a nonconstant real polynomial. The sequence $\{a_i\}_{i=1}^{\infty}$ of real numbers is strictly increasing and unbounded, as $$a_{i+1}<a_i+2020.$$The integers $\lfloor{|f(a_1)|}\rfloor$ , $\lfloor{|f(a_2)|}\rfloor$ , $\lfloor{|f(a_3)|}\rfloor$ , $\dots$ are written consecutively in such a way that their digits form an infinite sequence of digits $\{s_k\}_{k=1}^{\infty}$ (here $s_k\in\{0, 1, \dots, 9\}$). $\quad$If $n\in\mathbb{N}$ , prove that among the numbers $\overline{s_{n(k-1)+1}s_{n(k-1)+2}\cdots s_{nk}}$ , where $k\in\mathbb{N}$ , all $n$-digit numbers appear.
Problem
Source: Bulgaria National Olympiad 2020
Tags: algebra, integer part of polynomials
03.07.2020 21:58
First, we will show that any $t$ digit number $\ell$ appears as a number $\overline{s_{i+1}s_{i+2}\ldots s_{i+t}}$ for some $i\in \mathbb{N}$, or more precisely, that there is an $a_j$ such that the first $t$ digits of $\lfloor f(a_j)\rfloor$ are the same as of $\ell$ in the same order. Without loss of generality, assume that the leading coefficient of $f(x)=\sum_{i=0}^{m} b_i x^i$ is positive and that $a_i>0$ for all $i \in \mathbb{N}$. Claim 1. For large $i$, the difference between the number of digits of $ f(a_{i})$ and $ f(a_{i+1})-f(a_i)$ is arbitrarily large. Proof. Since the leading coefficient of $f$ is positive, there is some real $c$ such that $f(x)$ increases for $x>c$ because the derivative of $f$ can't have too many zeroes. The difference $f(a_{i+1})-f(a_{i})$ is at most $f(a_i +2020)-f(a_i)$ for $a_i>c$, and for the difference $d$ between the numbers of digits between $f(a_i)$ and $f(a_i+2020)-f(a_i)$ we have for large $a_i$ that \begin{align*} d &= \log{f(a_i)}-\log(f(a_i+2020)-f(a_i))\\ &=\log \left(\sum_{j=0}^{m} b_j a_{i}^j\right)-\log\left(\sum_{j=0}^{m}b_j \left((a_i+2020)^j-a_{i}^j)\right)\right) \\ &=\log \left(\frac{\sum_{j=0}^{m} b_j a_{i}^j}{\sum_{j=0}^{m}b_j \left((a_i+2020)^j-a_{i}^j)\right)}\right). \end{align*}This tells us that $d$ goes to infinity as $i$ gets large, because the denominator of the fraction in the logarithm is of degree less than the numerator, when considering as a polynomial on $a_i$, and this proves the claim. $\blacksquare$ Let $\ell$ be any $t$ digit number, choose $a_i$ such that $\lfloor f(a_i)\rfloor$ has more than $t$ digits and such that the difference between the number of digits of $f(a_{i})$ and $f(a_{i+1})-f(a_{i})$ is greater than $t+2$, this tells us that $\lfloor f(a_{i+1})\rfloor$ has the same first $t$ as $\lfloor f(a_{i})\rfloor$ unless there are a lot of consecutive $9$'s in the decimal expansion of $\lfloor f(a_{i})\rfloor$, but we can get rid of this case by considering the first $t+2$ digits of $\lfloor f(a_{i}) \rfloor$ to be $100\ldots 000$, and since the first $t$ digits of $f(a_{i+1})$ change by at most $1$ from those of $f(a_{i})$, we will eventually get the first digits of some $\lfloor f(a_j) \rfloor$ to be the same as $\ell$'s. Now, let $s$ be any fixed $n$ digit number, consider the number $ \ell=\overline{1s1s1s1s1s\ldots 1s}$ where there are $n$ ones, we know this number appears as $\overline{s_{i+1}s_{i+2}\ldots s_{i+n+n^2}}$ for some $i$, so the first digits of $s$'s in $\ell$ will be $s_{i+2}, s_{i+n+3}, \ldots, s_{i+n(n-1)+1}$ so for one of them their index will be $1 \pmod n$, and so we found a $k$ such that $s=\overline{s_{n(k-1)+1}s_{n(k-1)+1}\ldots s_{nk}}$. $\blacksquare$
09.07.2020 20:05
This was problem 6 of that competition. The author is Aleksandar Ivanov. I also commented it here.
21.10.2020 11:34
For any integer $x>10^{n-1}$, let $h(x)$ be its first $n$ digits. WLOG assume $f$ has positive leading coefficients, so $f$ is eventually increasing and unbounded. Let $$x_i=\lfloor|f(a_i)|\rfloor$$Let $b$ be a $n$-digit number. Define a b-chain to be a sequence $x_i,x_{i+1},...,x_{i+j}$ such that $$h(x_i)=h(x_{i+1})=...=h(x_{i+j})=b$$CLAIM. For each $b$ the length of a b-chain is strictly increasing and unbounded eventually Proof. Let $g(x)=f(x+2020)-f(x)$. Notice that $$\lim_{x\to\infty}\frac{g(x)}{f(x)}=0$$Hence $f(x_{i+1})-f(x_i)<g(x_i)=o(f(n))$. Hence the length of a chain is at the size of $\frac{f(x)}{g(x)}$ which is strictly increasing and unbounded.$\blacksquare$ Now take a sufficiently large integer $a$ with $(a,n)=1$. Then there're a sufficiently long chain such that each of its element has $a$ digits, so one of them must be in the position such that $b$ is included in the sequence $\{s\}$ as desired.