Kvant Math Problem 499
Consider what it means for a number to be balanced.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m14s
Source on kvant.digital
Problem
We call a number balanced if in its decimal representation some initial segment coincides with some terminal segment (for example, the numbers 1971, 19219 are balanced, whereas 1415145 is not). Prove that there exists a number which, after appending any of the 10 digits to its right, becomes balanced.
G. A. Gurevich
Exploration
Consider what it means for a number to be balanced. A number is balanced if there exists a nonempty prefix of its decimal representation that coincides exactly with a suffix. Small examples suggest that numbers with repeated patterns tend to be balanced: for instance, the number $121$ is balanced because the first digit $1$ coincides with the last digit, while $123123$ is balanced because $123$ occurs at both the start and end. Trying to append digits to a number generally breaks such coincidences unless the number has a very rigid repeating structure.
Testing small candidates, such as $0$, $1$, or $11$, shows that most short numbers fail to satisfy the requirement that appending any digit yields a balanced number. This indicates that the number we seek must be quite long and carefully structured. It appears promising to consider a number built from repeated concatenations of all digits in order so that any digit appended will complete a pattern that matches the beginning.
The crucial difficulty is constructing a number so that for any appended digit $d \in {0,1,\dots,9}$, some prefix equals some suffix in the resulting number. The key insight is that if we take a number that contains all possible finite strings of digits, in a specific order, the newly appended digit will always appear somewhere as a prefix and suffix, creating the balanced property.
Problem Understanding
The problem asks for a number such that appending any single digit results in a balanced number. This is a Type D problem because it requires a constructive existence argument. The core difficulty is ensuring that appending an arbitrary digit produces a suffix that matches some prefix, which requires a number with a highly encompassing combinatorial structure. Intuitively, a number containing every possible finite sequence of digits at least once will satisfy the requirement: appending a digit extends some previously occurring sequence, so a matching prefix and suffix will exist.
Proof Architecture
The proof will use the following lemmas. First, a number that contains every finite sequence of digits will allow any single-digit extension to yield a balanced number. Second, such a number exists and can be explicitly constructed by concatenating all finite digit strings in lexicographic order. Third, appending any digit to this number creates a suffix that coincides with some prefix because the appended digit completes a sequence already appearing at the start. The hardest part is rigorously showing that for any digit appended, the suffix coincides with a prefix rather than relying on intuition about "sufficiently long" sequences.
Solution
Construct a number $N$ by concatenating all finite sequences of decimal digits in lexicographic order: first the single-digit numbers $0,1,2,\dots,9$, then the two-digit numbers $00,01,02,\dots,99$, then the three-digit numbers $000,001,\dots,999$, and so on. Formally, let $S_k$ denote the list of all $k$-digit numbers in lexicographic order and define $N = S_1S_2S_3\dots$.
For any digit $d$, consider the number $N d$ obtained by appending $d$ to $N$. Since $N$ contains every finite sequence of digits, the sequence consisting of the last $k$ digits of $N d$ appears somewhere in $N$ as a prefix for a sufficiently large $k$. In particular, the sequence formed by the last $k$ digits ending with $d$ matches a prefix of $N$ of the same length, because every $k$-digit sequence occurs as a prefix of some $S_m$ within $N$ for some $m \ge k$. Therefore, $N d$ is balanced.
This argument holds for every digit $d \in {0,1,\dots,9}$, and hence $N$ satisfies the required property. The construction is explicit and ensures that any single-digit extension results in a balanced number.
This completes the proof.
∎
Verification of Key Steps
The most delicate step is the claim that appending a digit $d$ yields a suffix coinciding with a prefix. Independently, one can verify that for $k=1$, the last digit $d$ is among the single-digit prefixes $0,1,\dots,9$. For $k=2$, the last two digits form a two-digit number $xd$, which appears somewhere in $S_2$ as a prefix. Extending to higher $k$, any newly appended digit extends a finite sequence already present, ensuring that the suffix of appropriate length coincides with a prefix. This check confirms that the combinatorial coverage of all digit sequences guarantees the balanced property for all appended digits.
Another subtle point is confirming that concatenating sequences in lexicographic order does not skip any sequence. Each $S_k$ exhausts all $k$-digit numbers without repetition, and increasing $k$ ensures that every finite string occurs eventually, so the input to the previous step is valid.
Alternative Approaches
An alternative approach could attempt to construct a number with a more compact repeating pattern rather than concatenating all sequences. For example, one could try to use a de Bruijn sequence of a fixed order, which ensures that every $k$-digit string appears exactly once. The main approach is preferable because it does not require familiarity with de Bruijn sequences, scales naturally to cover all finite strings, and directly guarantees that appending any digit produces a balanced number without additional combinatorial arguments.