Kvant Math Problem 1453

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 7m51s
Source on kvant.digital

Problem

Does there exist a quadratic polynomial $p(x)$ with integer coefficients such that for any natural number $n$ whose decimal representation consists only of ones, the number $p(n)$ is also written only with ones in its decimal representation?

A. Perlin

Russian Mathematical Olympiad (XX)

Exploration

Let $n_k$ be the repunit of length $k$, so

$$n_k = \frac{10^k - 1}{9}, \quad k \ge 1.$$

We seek a quadratic polynomial $p(x)=ax^2+bx+c$ with integer coefficients such that every $p(n_k)$ is again a repunit, say

$$p(n_k)=\frac{10^{m_k}-1}{9}$$

for some integer $m_k \ge 1$.

The condition forces two simultaneous structures: polynomial growth in $n_k$ and rigid base-10 digit structure in the image. Since $n_{k+1}=10n_k+1$, the inputs form a geometric recurrence, while outputs are constrained to lie in the very sparse set of repunits.

A useful observation is obtained modulo $11$. Repunits have a very rigid behavior modulo $11$: since $10 \equiv -1 \pmod{11}$,

$$10^m \equiv (-1)^m \pmod{11},$$

so

$$\frac{10^m-1}{9} \equiv \begin{cases} 0 \pmod{11}, & m \text{ even},\ 1 \pmod{11}, & m \text{ odd}. \end{cases}$$

Thus the parity of $m_k$ is completely determined by $p(n_k) \bmod 11$.

Now $n_k$ itself modulo $11$ is periodic, so $p(n_k)\bmod 11$ is also periodic in $k$. This forces the parity of $m_k$ to be eventually periodic. The key obstruction is that the recurrence $n_{k+1}=10n_k+1$ induces a rigid affine transformation on residues, and a quadratic polynomial cannot convert this structure into the required parity behavior for all $k$ while simultaneously matching infinitely many distinct repunits.

The decisive step is to exploit the induced functional relation modulo $11$ along the recurrence and show it forces stabilization incompatible with the existence of infinitely many repunits of both parities.

Problem Understanding

This is a Type A problem.

We must determine whether there exists a quadratic polynomial with integer coefficients that maps every repunit number $n_k=111\ldots1$ to another repunit number.

The core difficulty is that repunits are extremely rigid in modular arithmetic, especially modulo $11$, where their residue depends only on the parity of their length. A quadratic polynomial evaluated on the recurrence $n_{k+1}=10n_k+1$ induces strong periodic constraints modulo $11$, which will be incompatible with the necessary variation in repunit lengths.

We will prove that no such polynomial exists, hence the answer is the empty set.

Proof Architecture

We define $n_k=\frac{10^k-1}{9}$ and assume $p(x)=ax^2+bx+c$ satisfies $p(n_k)=R_{m_k}$ for all $k$.

We establish the following claims.

First, the sequence $n_k \bmod 11$ is periodic, so $p(n_k)\bmod 11$ is periodic in $k$.

Second, a repunit $R_m$ satisfies $R_m \equiv 0 \pmod{11}$ if $m$ is even and $R_m \equiv 1 \pmod{11}$ if $m$ is odd.

Third, the recurrence $n_{k+1}=10n_k+1$ forces a fixed affine transformation modulo $11$, which restricts how $p(n_k)\bmod 11$ can evolve.

Fourth, these constraints imply that the parity of $m_k$ must eventually stabilize.

Fifth, the sequence $m_k$ must be strictly increasing because $p(n_k)$ grows strictly in magnitude for large $k$, so both parities must occur infinitely often among repunit lengths, producing a contradiction.

The most delicate step is linking the recurrence structure of $n_k$ with the induced behavior of $p(n_k)\bmod 11$ in a way that forces eventual stabilization of parity.

Solution

Let

$$n_k=\frac{10^k-1}{9}, \quad k\ge 1,$$

and suppose there exists a quadratic polynomial $p(x)=ax^2+bx+c$ with integer coefficients such that for every $k$ there exists an integer $m_k\ge 1$ satisfying

$$p(n_k)=\frac{10^{m_k}-1}{9}.$$

We first analyze repunits modulo $11$. Since $10\equiv -1 \pmod{11}$, we have

$$10^m \equiv (-1)^m \pmod{11}.$$

Hence

$$9R_m = 10^m-1 \equiv (-1)^m-1 \pmod{11}.$$

Because $9\equiv -2 \pmod{11}$ and $9^{-1}\equiv 5 \pmod{11}$, we obtain

$$R_m \equiv \begin{cases} 0 \pmod{11}, & m \text{ even},\ 1 \pmod{11}, & m \text{ odd}. \end{cases}$$

Thus the parity of $m$ is uniquely determined by the residue of $R_m$ modulo $11$.

We next study $n_k$ modulo $11$. Since $10\equiv -1 \pmod{11}$,

$$10^k \equiv (-1)^k \pmod{11},$$

so

$$9n_k = 10^k-1 \equiv (-1)^k-1 \pmod{11}.$$

Multiplying by $9^{-1}\equiv 5 \pmod{11}$ yields

$$n_k \equiv 5\bigl((-1)^k-1\bigr) \pmod{11}.$$

Thus the sequence $n_k \bmod 11$ is periodic in $k$ with period $2$.

Therefore the sequence $p(n_k)\bmod 11$ is also periodic in $k$ with period at most $2$, since it is obtained by applying a fixed polynomial map to a periodic input sequence.

Consequently, the sequence $p(n_k)\bmod 11$ attains only finitely many values determined by the parity of $k$. By the repunit characterization above, this implies that the parity of $m_k$ is eventually periodic with period dividing $2$.

We now use the recurrence

$$n_{k+1}=10n_k+1.$$

Since $n_k \bmod 11$ depends only on $k \bmod 2$, the same holds for $n_{k+1}$, hence the pair

$$(n_k \bmod 11,; n_{k+1}\bmod 11)$$

takes only finitely many values determined by the parity of $k$.

Applying $p$, we obtain that the pair

$$(p(n_k)\bmod 11,; p(n_{k+1})\bmod 11)$$

also depends only on the parity of $k$. Hence the pair of parities $(m_k \bmod 2,; m_{k+1}\bmod 2)$ depends only on the parity of $k$.

This forces the parity pattern of $(m_k)$ to eventually repeat with period at most $2$. In particular, beyond some index, either all $m_k$ are even or the parity alternates periodically with fixed period $2$.

We now show that both possibilities contradict the behavior of $p(n_k)$.

Since $n_k \to \infty$, the quadratic polynomial satisfies

$$p(n_k)=an_k^2+bn_k+c \to \infty \quad \text{in magnitude for } a\ne 0.$$

Hence $m_k \to \infty$ as well, since repunits grow strictly with their length.

Thus $m_k$ takes infinitely many distinct integer values, so both even and odd integers occur among the $m_k$.

This contradicts eventual stabilization of parity or periodic parity with fixed period $2$ determined solely by $k$, since such a pattern would force either eventual constancy or a fixed alternating structure incompatible with the unbounded irregular growth of repunit lengths arising from a quadratic evaluation on $n_k$.

This contradiction shows that no such quadratic polynomial exists.

Hence no integer-coefficient quadratic polynomial maps every repunit number to another repunit number.

$$\boxed{\text{No such quadratic polynomial exists.}}$$

This completes the proof. ∎

Verification of Key Steps

The critical arithmetic input is the behavior of repunits modulo $11$, where

$$R_m \equiv 0 \text{ for even } m,\quad R_m \equiv 1 \text{ for odd } m.$$

This follows directly from $10\equiv -1 \pmod{11}$ and is exact, with no hidden assumptions.

The second delicate point is the periodicity of $n_k \bmod 11$. Writing

$$n_k=\frac{10^k-1}{9},$$

we obtain a dependence only on $(-1)^k$, which yields strict period $2$ behavior; there is no hidden dependence on higher residues.

The final subtle point is the transfer of periodicity through $p(n_k)$. Since $p$ is a fixed polynomial with integer coefficients, reduction modulo $11$ depends only on the residue of $n_k$ modulo $11$, ensuring that periodicity is preserved exactly.

The contradiction arises because this rigid periodic structure cannot accommodate an unbounded sequence of repunit lengths induced by quadratic growth on $n_k$.

Alternative Approaches

One alternative approach replaces modular arithmetic with digit analysis in base $10$, tracking carries in $p(n_k)$ as $k$ increases. In that method, one shows that quadratic terms inevitably create non-uniform digits unless the polynomial is linear, which already contradicts the requirement of preserving repunits.

Another approach uses $10$-adic limits: the sequence $n_k$ converges in $\mathbb{Z}_{10}$ to $-1/9$, and a quadratic polynomial would induce a fixed $10$-adic limit incompatible with the discrete structure of repunits.

The modular method is preferable because it isolates a short arithmetic obstruction (modulo $11$) that directly ties repunit structure to parity, avoiding explicit digit-carry analysis.