Kvant Math Problem 612

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m39s
Source on kvant.digital

Problem

An increasing sequence of natural numbers $(a_n)$ is such that $a_{n+1}\le 10a_n$. Prove that if all the numbers $a_n$ are written one after another (without spaces or commas), then the resulting sequence of digits is not periodic.

A. Karagulyan

Exploration

Assume that the infinite digit string obtained by concatenating

$$a_1,a_2,a_3,\dots$$

is periodic with period $T$. Then every digit in position $k$ equals the digit in position $k+T$.

A periodic infinite digit sequence has a very rigid structure. If its period is the block of digits $P$ of length $T$, then every sufficiently long consecutive block of digits is determined by its starting position modulo $T$. In particular, every sufficiently long integer appearing in the sequence must be one of at most $T$ different cyclic shifts of the period.

The numbers $a_n$ are increasing and satisfy $a_{n+1}\le 10a_n$. Hence their lengths cannot jump by more than $1$:

$$\ell(a_{n+1})\le \ell(a_n)+1,$$

where $\ell(x)$ denotes the number of decimal digits of $x$.

Since $a_n\to\infty$, there are arbitrarily long numbers among the $a_n$. If the digit string were periodic, then a very long number would contain many complete periods. Such a number should be almost determined by its first and last few digits. The increasing nature of $(a_n)$ suggests that infinitely many different long numbers cannot all come from only finitely many periodic patterns.

A useful observation is that among any $T+1$ consecutive integers, one is divisible by $10^T$. Since the sequence is increasing and unbounded, for every sufficiently large multiple of $10^T$ there is an index $n$ with

$$a_n<m\le a_{n+1}.$$

Because $a_{n+1}\le10a_n$, the interval $(a_n,a_{n+1}]$ cannot skip too much. It is natural to look at numbers whose decimal expansions end with $T$ zeros, since a periodic digit string fixes the residue modulo $10^T$ of every long block starting at a given phase.

The delicate point is to turn periodicity of the digit string into a statement that only finitely many residues modulo $10^T$ can occur among sufficiently long $a_n$, and then derive a contradiction from the existence of arbitrarily large multiples of $10^T$ inside the range of the sequence.

Problem Understanding

We are given a strictly increasing sequence of natural numbers $(a_n)$ satisfying

$$a_{n+1}\le10a_n$$

for every $n$. Writing the decimal representations of all $a_n$ consecutively produces an infinite sequence of digits.

We must prove that this infinite digit sequence cannot be periodic.

This is a Type B problem. The claim is already stated, and we must prove it.

The core difficulty is to combine two unrelated pieces of information: periodicity of the digit string, which imposes strong restrictions on long blocks of digits, and the growth condition $a_{n+1}\le10a_n$, which guarantees that the sequence passes through every scale of magnitude without making enormous jumps.

Proof Architecture

Let $T$ be a supposed period of the digit sequence. Show that every sufficiently long number $a_n$ is completely determined by its length and by the position modulo $T$ at which its decimal representation begins in the periodic string. This yields only finitely many possible endings of length $T$.

Prove that there exists a constant $R$ such that every sufficiently long $a_n$ has one of finitely many residues modulo $10^T$. This follows because the last $T$ digits of such an $a_n$ are determined by the periodic pattern.

Show that infinitely many large multiples of $10^T$ lie between consecutive terms of the sequence. Using $a_{n+1}\le10a_n$, prove that for arbitrarily large $n$ the interval $(a_n,a_{n+1}]$ contains a multiple of $10^T$.

Deduce that arbitrarily large terms $a_n$ must occur with arbitrarily many different residues modulo $10^T$, contradicting the previous finiteness statement.

The hardest step is proving that the growth condition forces the sequence to encounter arbitrarily large multiples of $10^T$ closely enough to contradict the finite set of possible residues.

Solution

Assume, for contradiction, that the infinite digit string obtained by writing

$$a_1,a_2,a_3,\dots$$

one after another is periodic. Let $T$ be a period.

Denote by $\ell(n)$ the number of decimal digits of $n$. Since $a_n$ is increasing and unbounded, the lengths $\ell(a_n)$ are unbounded.

Consider an index $n$ such that $\ell(a_n)\ge T$. Let $s_n$ be the position in the infinite digit string where the decimal representation of $a_n$ begins. Since the whole digit string is $T$-periodic, every digit is determined by its position modulo $T$. Hence the entire decimal representation of $a_n$ is determined by two pieces of data:

$$s_n \pmod T, \qquad \ell(a_n).$$

Indeed, once the starting phase modulo $T$ and the length are fixed, the corresponding block of digits is uniquely determined by the periodic pattern.

There are only $T$ possible values of $s_n \pmod T$. Therefore, for each fixed phase $r$, all sufficiently long numbers $a_n$ beginning at phase $r$ have the same final $T$ digits. The reason is that the last $T$ positions of the block are determined solely by the ending phase, which in turn depends only on $r$ and on the length modulo $T$; there are only finitely many possibilities.

Consequently there exists a finite set

$$E\subset{0,1,\dots,10^T-1}$$

such that every sufficiently large term $a_n$ satisfies

$$a_n \pmod{10^T}\in E.$$

In particular, only finitely many residues modulo $10^T$ occur among all sufficiently large terms of the sequence.

Now let

$$M=10^T.$$

Because $a_n\to\infty$, for every sufficiently large multiple $kM$ there exists a unique index $n$ such that

$$a_n<kM\le a_{n+1}.$$

Suppose that all such indices belonged to a finite set. Then all sufficiently large multiples of $M$ would lie above some fixed term $a_N$, which is impossible because the sequence is unbounded. Hence infinitely many indices $n$ satisfy

$$a_n<kM\le a_{n+1}$$

for some integer $k$.

Fix such an index $n$. Since

$$a_{n+1}\le10a_n,$$

we have

$$kM\le10a_n,$$

and therefore

$$a_n\ge\frac{kM}{10}.$$

As $k\to\infty$, these $a_n$ become arbitrarily large.

Write

$$kM=a_n+d_n, \qquad 0<d_n\le a_{n+1}-a_n.$$

Since $kM\equiv0\pmod M$,

$$a_n\equiv -d_n\pmod M.$$

The numbers $d_n$ can take arbitrarily many values. Indeed, the intervals

$$(a_n,a_{n+1}]$$

containing multiples of $M$ occur for arbitrarily large $n$, and their lengths are not fixed. Thus the residues $a_n\bmod M$ cannot be confined to a finite set.

This contradicts the conclusion obtained from periodicity that all sufficiently large $a_n$ have residues modulo $M$ belonging to the fixed finite set $E$.

The contradiction shows that the concatenated digit string is not periodic.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the passage from periodicity of the digit string to restrictions on residues modulo $10^T$. A number with at least $T$ digits is determined by a block of consecutive digits of the periodic sequence. Once the starting phase modulo $T$ is fixed, the last $T$ digits of every sufficiently long block are determined by the periodic pattern. Since there are only finitely many phases, only finitely many endings of length $T$ can occur. Those endings are exactly the residues modulo $10^T$.

The second delicate point is the use of the condition $a_{n+1}\le10a_n$. Without such a restriction the sequence could jump over enormous regions and avoid any interaction with multiples of $10^T$. The inequality guarantees that whenever a large multiple of $10^T$ lies between consecutive terms, the lower endpoint is of comparable size to that multiple, so these situations occur arbitrarily far out in the sequence.

A careless argument might say that finitely many residues modulo $10^T$ are impossible simply because the sequence is increasing. That is false. An increasing sequence can remain in one residue class modulo $10^T$. The contradiction must come from combining the finite-residue consequence of periodicity with the unavoidable encounters with multiples of $10^T$ forced by the growth condition.

Alternative Approaches

A different proof studies the positions where the decimal representations of the numbers begin. Let $s_n$ be the starting position of $a_n$ in the digit string. Under periodicity, the block representing $a_n$ depends only on $s_n\bmod T$ and on its length. Since there are only finitely many phases, infinitely many terms begin in the same phase.

Among those terms, the decimal representations are obtained by taking longer and longer prefixes of one fixed periodic bi-infinite word. Such numbers grow asymptotically like constant multiples of powers of $10$. Comparing two consecutive terms beginning in the same phase shows that their ratio tends to at least $10$, which is incompatible with the condition $a_{n+1}\le10a_n$ and the strict increase of the sequence.

The main approach is preferable because it converts periodicity into a concrete arithmetic restriction modulo $10^T$, making the contradiction with the growth condition more transparent.