Let $c$ be a fixed positive integer, and let ${a_n}^{\inf}_{n=1}$ be a sequence of positive integers such that $a_n < a_{n+1} < a_n+c$ for every positive integer $n$. Let $s$ denote the infinite string of digits obtained by writing the terms in the sequence consecutively from left to right, starting from the first term. For every positive integer $k$, let $s_k$ denote the number whose decimal representation is identical to the $k$ most left digits of $s$. Prove that for every positive integer $m$ there exists a positive integer $k$ such that $s_k$ is divisible by $m$.
Problem
Source: MOP 2006 Homework - Black Group
Tags: number theory unsolved, number theory
05.05.2014 18:45
Just note that for some sufficiently large $n$, some $a_n$ needs to have its left most $m$ digits all be 1's. Thus is because there exists some sufficiently large $n$ such that $10^n > c$, so some $a_n$ needs to fall in the range $[11...11 \cdot 10^n, 11...12 \cdot 10^n)$.
10.04.2020 23:51
@above's solution is wrong, I think he mistook $s_k$ for the sum of digits of $s_k.$ My solution: Denote by $d(n)$ the number of digits of $n.$ Let $u=2^{\alpha}5^{\beta}$ and $m=uv$ with $v \in \mathbb{N}$ and $\gcd(10,v)=1.$ Lemma: there exists $K$ with $\phi(v) \mid d(K) > max\{ \alpha, \beta \}$ and $v \mid K-1.$ Proof: In $[10^{m \phi(x)-1}, 10^{m \phi(x)-1}+m]$ there is some $T$ with $m \mid T-1.$ Then $T \cdot 10^{\phi(x) \cdot max\{ \alpha, \beta \}}$ satisfies the conditions. Now consider $\overline{K...K}=y_j$ where there are $j$ consecutive $K$'s. There is $a_n \in [y_{2m} \cdot 10^{a_1+c}, y_{2m} \cdot 10^{a_1+c+1})$ (because $a_n$ increases less than $10^{a_1+c}$ in each step). Take the least such $a_n$, say it is $a_{p+1}.$ We have $a_1<a_{p+1}$ so $p \in \mathbb{N}.$ Then each $\overline{a_1...a_p}=r_0, \overline{a_1...a_py_1}=r_1, ..., \overline{a_1....a_py_{2m}}=r_{2m}$ is a $s_i$. We prove that $m$ divides some of these numbers. Notice that $r_{n+1}=r_n10^{d(K)}+K \equiv r_n+1 \pmod{v}$ so for some $l>0$ we have $v \mid r_l$. But $r_l=r_{l-1}10^{d(K)}+K$ is divisible by $u$ and $\gcd(u,v)=1$, and it implies $m \mid r_l$, which is a $s_i.$