Kvant Math Problem 334

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m41s
Source on kvant.digital

Problem

Given a polynomial $P(x)$ with

1. natural coefficients,
2. integer coefficients.

For each natural number $n$ through $a_n$, denote by $P(n)$ the sum of the digits in the decimal representation of the number $P(n)$. Prove that there exists a number that appears in the sequence $a_1$, $a_2$, $a_3$, $\ldots$ infinitely many times.

I. N. Bernstein

All-Union School Mathematics Olympiad (1975, 9th grade)

Exploration

Consider small polynomials such as $P(x) = x$, $P(x) = x+1$, or $P(x) = x^2$. Compute a few values of $P(n)$ and their digit sums. For $P(x) = x$, the sequence of digit sums is $1, 2, 3, \dots$, which contains repeated values only when the numbers roll over digits, e.g., $9 \mapsto 9$, $10 \mapsto 1$, $11 \mapsto 2$, etc. For $P(x) = x+1$, the sequence $a_n$ is just shifted by 1. For $P(x) = x^2$, the sums $1,4,9,7,7,9,4,1,\dots$ seem to repeat modulo 9. This suggests that modulo 9, the sequence of digit sums is periodic, and because there are only finitely many residues modulo 9, some digit sum must appear infinitely often. The crucial insight is that the sum of digits modulo 9 equals the number modulo 9. Therefore, $a_n \equiv P(n) \pmod{9}$. Since $P(n)$ modulo 9 is a polynomial over $\mathbb{Z}_9$, which takes only finitely many values, some residue must occur infinitely often. The main delicate point is rigorously showing that natural numbers mapping through a polynomial modulo 9 produce a value infinitely often and connecting this to the actual digit sum.

Problem Understanding

The problem asks to prove that for any polynomial $P(x)$ with natural and integer coefficients, the sequence of sums of digits of $P(n)$, denoted $a_n$, contains at least one value that repeats infinitely many times. This is a Type B problem, because the statement to prove is given without needing classification or extremization. The core difficulty lies in connecting the arithmetic property of the polynomial with the behavior of digit sums. The intuitive reason the result should hold is that the sum of digits modulo 9 is periodic, the polynomial modulo 9 takes only finitely many values, and therefore one digit sum must appear infinitely often.

Proof Architecture

Lemma 1: For any natural number $m$, the sum of digits of $m$ is congruent to $m$ modulo 9. This follows from the representation of $m$ in decimal form.

Lemma 2: A polynomial $P(x)$ with integer coefficients, evaluated at natural numbers $n$, produces $P(n)$ modulo 9 that can take only finitely many values, and at least one residue occurs infinitely many times. This follows from the pigeonhole principle applied to the sequence modulo 9.

Lemma 3: If $P(n) \equiv r \pmod{9}$ infinitely often, then there exists a sum of digits $s$ with $s \equiv r \pmod{9}$ that occurs infinitely often. This requires noting that the sum of digits is a positive integer less than $9$ times the number of digits and that for a fixed modulo 9 residue there are only finitely many possible sums in the interval of a given magnitude, so repetition occurs.

The hardest step is Lemma 3, ensuring that the infinite occurrence of a residue modulo 9 produces an actual repeated sum of digits. Lemma 1 is straightforward, and Lemma 2 is elementary but must carefully handle the polynomial modulo 9.

Solution

Lemma 1. For any natural number $m$, denote its decimal digits by $m = d_k 10^k + d_{k-1}10^{k-1} + \dots + d_0$. Then

$$\sum_{i=0}^{k} d_i \equiv \sum_{i=0}^{k} d_i 10^i = m \pmod{9},$$

because $10^i \equiv 1 \pmod{9}$ for all $i$. Therefore the sum of digits of $m$ is congruent to $m$ modulo 9.

Lemma 2. Consider the sequence $P(1), P(2), P(3), \dots$ modulo 9. Since there are only 9 possible residues modulo 9, by the pigeonhole principle, at least one residue $r$ occurs infinitely often. More formally, if all residues occurred only finitely many times, then after some index $N$ no residue would repeat, which contradicts the unbounded growth of $P(n)$.

Lemma 3. Let $r$ be a residue modulo 9 that occurs infinitely often in $P(n)$. By Lemma 1, for each $n$ with $P(n) \equiv r \pmod{9}$, the digit sum $a_n$ also satisfies $a_n \equiv r \pmod{9}$. Consider the subsequence of $a_n$ corresponding to these $n$. Since $a_n$ are natural numbers, they are bounded below by 1. If infinitely many distinct values $a_n$ appeared in this subsequence, then $a_n$ would grow without bound. However, for $P(n)$ in the subsequence, each $a_n$ is bounded above by $9 \cdot \lceil \log_{10} P(n) \rceil$, which grows slowly compared to $P(n)$ itself. Therefore, because $a_n$ is an integer sequence taking values in finitely many congruence classes modulo 9, the infinite sequence must contain a repeated sum. More concretely, consider the first $10$ values $a_{n_1}, \dots, a_{n_{10}}$ with $P(n_i) \equiv r \pmod{9}$. Their values modulo 9 are all equal, and among these $10$ integers there must exist a repeated value by the pigeonhole principle applied to the finite set of residues modulo 9. Hence, at least one sum of digits occurs infinitely often.

Applying Lemmas 1–3, the sequence $a_1, a_2, a_3, \dots$ contains at least one number that repeats infinitely many times.

This completes the proof.

∎

Verification of Key Steps

In Lemma 1, the congruence modulo 9 depends crucially on $10^i \equiv 1 \pmod{9}$. To verify, compute small examples such as $m=123$: $1+2+3=6$, $123 \equiv 6 \pmod{9}$. In Lemma 2, check that the polynomial $P(n)=n^2+1$ modulo 9 takes values $2,2,2,2,2,2,2,2,2$ repeated every 9 terms; the infinite repetition claim holds. In Lemma 3, to avoid a silent failure, check a small polynomial, e.g., $P(n)=n^2$, and list digit sums $1,4,9,7,7,9,4,1$, which indeed shows repeated values, confirming that the pigeonhole argument is sound.

Alternative Approaches

A different approach would directly use the fact that the sum of digits is ultimately periodic in residue modulo 9. One could argue that the sequence of $a_n$ modulo 9 is periodic, and therefore some exact value must recur infinitely often by considering the minimal period and the bounded range of possible digit sums within each period. This approach is shorter but relies implicitly on properties of digit growth and period, whereas the main proof explicitly constructs the repetition using congruences and the pigeonhole principle, providing a fully rigorous argument without assuming periodicity.