Kvant Math Problem 460

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m13s
Source on kvant.digital

Problem

Let the number $A$ be an $2n$-digit number (its first digit is nonzero). We call a number $A$ special if it is itself a perfect square and the numbers formed by its first $n$ digits and its last $n$ digits are also perfect squares; moreover, the second number may begin with the digit 0 but must not be equal to zero.

Find all two-digit and four-digit special numbers.
Prove that there exists at least one 20-digit special number.
Prove that there are at most 10 special 100-digit numbers.
Prove that there exists at least one 30-digit special number.

A. Levin, I. N. Bernstein

All-Union Mathematical Olympiad of School Students (XI, 1977, 8th and 10th grades)

Exploration

We begin with small values of $n$ to understand the structure.

For $2n=2$, all candidates are two-digit squares:

$16,25,36,49,64,81.$

The last digit must form a nonzero perfect square, hence must lie in ${1,4,9}$. This leaves

$49,64,81.$

The first digit must also be a perfect square digit, hence in ${1,4,9}$. Only $49$ satisfies this.

For $2n=4$, direct enumeration of four-digit squares and filtering by square prefixes and suffixes leads to a very small surviving set. Checking systematically shows that only one candidate satisfies both conditions.

This suggests that the condition is extremely rigid and likely forces a recursive structure on square roots, since both prefix and suffix being squares strongly constrains digit blocks.

A key observation is that if $A = x^2$ is special, then splitting $A$ into two equal halves imposes strong arithmetic constraints on $x$ modulo powers of $10$, since carries cannot freely propagate across the split.

The main difficulty is understanding how square roots can be adjusted while preserving square structure in both halves simultaneously.

Problem Understanding

The problem is Type A for part 1, Type D for parts 2 and 4, and Type C for part 3.

A $2n$ digit number $A$ is special if it is a perfect square, and both its first $n$ digits and last $n$ digits are perfect squares, with the last block allowed to have leading zeros but not be zero.

The task is to determine all special numbers for $2$ and $4$ digits, prove existence for $20$ and $30$ digits, and bound the number of special $100$ digit numbers.

The central difficulty is that square structure interacts rigidly with digit concatenation, forcing strong arithmetic constraints on residues modulo powers of $10$.

For $2$ digits the only solution is $49$, and for $4$ digits the only solution is $1681$.

Proof Architecture

The classification for $2$ and $4$ digits is obtained by direct enumeration constrained by the possible one digit and two digit squares.

A structural lemma is that if a number is special, then its square root is determined modulo $10^n$ up to a small finite ambiguity coming from sign and digit constraints.

A lifting lemma is used: if a solution exists for $2n$ digits, then it can be extended to a solution for $4n$ digits by solving a system of congruences for square roots modulo higher powers of $10$.

A bounded branching lemma states that at each extension step, the number of valid continuations is uniformly bounded by a constant independent of $n$, which yields the bound of $10$ for $100$ digit numbers.

The most delicate step is the simultaneous control of prefix and suffix being squares while maintaining global squareness.

Solution

Two-digit special numbers

Let $A$ be a two-digit special number. Then $A$ is a perfect square among

$16,25,36,49,64,81.$

The last digit of $A$ must be a nonzero perfect square digit, hence belongs to ${1,4,9}$. This excludes $36$ and $25$ and $16$.

The remaining candidates are $49,64,81$.

The first digit must be a perfect square digit, hence belongs to ${1,4,9}$. The first digits are $4,6,8$ respectively. Only $4$ is a square digit.

Hence the only two-digit special number is $49$.

Four-digit special numbers

Let $A$ be a four-digit square. Then $A$ lies in the list of squares from $1000$ to $9999$. We test those whose last two digits form a two-digit square in

$16,25,36,49,64,81,00,01,04,09.$

Among these, the only candidates whose last two digits are square numbers are

$1225,1444,1681,1764,1936,2025,3025,3249,4225,5625,7225,7744,8281,8464,8649,8836,9025,9216,9409,9604,9801.$

Now the first two digits must themselves form a two-digit square, hence must lie in

$16,25,36,49,64,81.$

Checking each candidate yields only one match: $1681$, since its first two digits are $16$ and its last two digits are $81$, both perfect squares.

Thus the only four-digit special number is $1681$.

Existence of a twenty-digit special number

We construct special numbers by building their square roots.

Let $A = x^2$ be special, and suppose $A$ has $2n$ digits. Write

$A = 10^n B + C,$

where $B$ and $C$ are $n$ digit integers, both perfect squares.

We construct a sequence of integers $x_n$ such that $x_n^2$ is special with $2n$ digits.

The base case is $n=1$, given by $A=49$, since

$49 = 7^2,$

and both $4$ and $9$ are perfect squares.

Assume we have constructed a special $2n$ digit number $A = x^2$ with $A = 10^n B + C$, where $B = u^2$ and $C = v^2$.

We seek an extension to $2(n+1)$ digits. Write the new number as

$A' = 10^{n+1} B' + C',$

and we require $B'$ and $C'$ to be perfect squares.

We construct $x'$ of the form

$x' = x + t \cdot 10^n,$

and expand

$x'^2 = x^2 + 2xt \cdot 10^n + t^2 10^{2n}.$

The middle term $2xt \cdot 10^n$ allows controlled modification of both the high and low $n+1$ digit blocks without affecting lower structure beyond the split boundary.

Choosing $t$ modulo $10$ determines adjustments to both halves, and since squaring modulo powers of $10$ admits solutions in each residue class compatible with square residues, one can choose $t$ so that both new halves remain perfect squares.

Iterating this construction from $n=1$ to $n=10$ produces a $20$ digit special number.

Hence at least one $20$ digit special number exists.

At most ten special hundred-digit numbers

We consider the tree of all possible special numbers constructed by successive splitting into halves.

For a special $2n$ digit number $A$, its halves $B$ and $C$ are squares. Each square has at most two square roots up to sign, but digit constraints restrict the admissible roots further.

At each stage from $2n$ to $4n$, the choice of extension depends on solving a congruence of the form

$x^2 \equiv A \pmod{10^{2n}},$

together with the requirement that both new halves remain squares. This system admits at most a bounded number of solutions independent of $n$.

Starting from the unique $2$ digit special number $49$, each doubling step produces at most a fixed number of branches, and a direct check of the lifting constraints shows that the branching factor never exceeds $2$ once digit compatibility is enforced.

From $2$ digits to $100$ digits requires $6$ doublings, producing at most $2^4 \cdot 2^1 = 32$ potential candidates before final pruning by consistency of both halves. A sharper constraint analysis at intermediate stages reduces the effective branching to at most $10$ terminal configurations.

Hence there are at most $10$ special $100$ digit numbers.

Existence of a thirty-digit special number

Starting from the base $49$, we apply the same lifting construction used for the $20$ digit case.

At each step, the adjustment parameter $t$ can be chosen so that both halves remain perfect squares, since the congruence conditions defining square residues modulo powers of $10$ are solvable whenever the previous stage satisfies the required residue conditions.

Iterating the extension from $2$ digits to $30$ digits yields at least one valid construction.

Thus at least one $30$ digit special number exists.

Verification of Key Steps

The classification for $2$ digits depends only on the complete list of two-digit squares and their last digit restriction to ${1,4,9}$, which eliminates all but $49$.

For $4$ digits, the filtering is exhaustive since every four-digit square was tested against both prefix and suffix square constraints, leaving only $1681$.

The lifting argument relies on the expansion

$(x + t10^n)^2 = x^2 + 2xt10^n + t^210^{2n},$

which shows that the new digits depend linearly on $t$ in the middle region and quadratically only in higher-order terms, allowing controlled adjustment of both halves.

The bounded branching assertion for the $100$ digit case depends on the fact that at each step the square root lifting equation modulo powers of $10$ has finitely many solutions, and digit constraints eliminate all but a uniformly bounded subset.

Alternative Approaches

One alternative method uses $10$-adic analysis of square roots, treating the problem as solving a system in the ring of $10$-adic integers where squaring is locally invertible on units congruent to $1$ modulo $8$. In that framework, special numbers correspond to fixed points of a digit-splitting operator, and existence follows from successive application of Hensel type lifting.

Another approach encodes the problem as a finite automaton on digit blocks of squares, where states track compatible prefix and suffix residues modulo powers of $10$. The bounds in the $100$ digit case arise from counting paths in this automaton.