Kvant Math Problem 373

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

Problem

1. All natural numbers (written in decimal notation) are divided into two classes. Prove that any infinite decimal expansion can be split into finite pieces such that all of them, except possibly the first piece, belong to the same class.
2. The same problem, but the natural numbers are divided not into two, but into several classes.

Exploration

An infinite decimal expansion determines an infinite sequence of digits, hence an infinite word over the alphabet ${0,1,\dots,9}$. Cutting it into finite pieces means choosing an increasing sequence of indices $0=i_0<i_1<i_2<\cdots$ and forming blocks as the digit strings between consecutive cut points. Each block is then interpreted as a natural number in decimal notation, so each block inherits a class from a fixed partition of $\mathbb{N}$ into finitely many colors.

The task is to force all blocks except possibly the first to lie in a single fixed class, despite having complete freedom in choosing cut points but no control over the coloring. This suggests an infinite pigeonhole principle applied not to individual numbers, but to infinitely many choices of suffixes from each position.

From any fixed starting position $i$, there are infinitely many possible next cut points $j>i$, hence infinitely many candidate block values. Since only finitely many classes exist, at least one class occurs infinitely often among these candidates. The difficulty is that the “frequently occurring” class may depend on the starting position, so a consistent global class must be extracted along an infinite chain of positions.

The key point is to construct an infinite sequence of cut points together with a single class that remains infinitely extendable at every step.

Problem Understanding

This is a Type D existence problem.

Given any coloring of natural numbers into finitely many classes, and any infinite digit sequence, we must construct a partition of the sequence into finite consecutive blocks such that all blocks except possibly the first belong to the same class.

Equivalently, from any infinite sequence of integers produced by all possible contiguous substrings, we must extract an infinite chain of consecutive substrings whose values lie in a single fixed color class.

The intuitive reason this should hold is that from every position there are infinitely many possible next blocks, so one color class must recur infinitely often in a sufficiently coherent way to allow an infinite recursive construction.

Proof Architecture

The proof first reformulates the problem in terms of choosing an infinite increasing sequence of cut points.

A first lemma states that from any position and any fixed color class, either there are finitely many extensions in that class or infinitely many; this dichotomy follows directly from finiteness of classes.

A second lemma constructs a color class $c$ such that from the initial position there are infinitely many cut points reachable with color $c$, and among those cut points one can select infinitely many that preserve the same property recursively.

A third lemma constructs by induction an infinite sequence of cut points such that each consecutive block has color $c$.

The hardest point is the recursive preservation of infinite extendability under restriction to chosen cut points, since naive pigeonhole selection does not guarantee persistence of the property.

Solution

Let the given infinite decimal expansion define digits $d_1,d_2,\dots$. For indices $0\le i<j$, denote by $A(i,j)$ the natural number formed by the block $d_{i+1}\dots d_j$. The natural numbers are partitioned into finitely many classes $C_1,\dots,C_m$.

For each index $i$ and each class $C_k$, define the set

$$S_i(k)={j>i : A(i,j)\in C_k}.$$

For each fixed $i$, the union of all $S_i(k)$ over $k=1,\dots,m$ equals the set of all integers greater than $i$, hence is infinite. Since there are finitely many classes, at least one index $k$ satisfies that $S_i(k)$ is infinite for every $i$ in an infinite subset of $\mathbb{N}$; otherwise, if each class had only finitely many such $i$, the union over all classes would be finite, contradicting the fact that for every $i$ there exists some $k$ with infinitely many extensions.

Choose a class $C$ such that there exist infinitely many indices $i$ for which $S_i(C)$ is infinite. Let $T_0$ be the set of all such indices. Then $T_0$ is infinite.

Construct inductively an increasing sequence $i_0<i_1<i_2<\cdots$ with $i_0=0$ and $i_1\in T_0$ chosen such that $i_1\in S_0(C)$. Having chosen $i_n$, consider the set $S_{i_n}(C)$. If $i_n\in T_0$, then by definition $S_{i_n}(C)$ is infinite. Among the elements of $S_{i_n}(C)$, at least one lies in $T_0$, because otherwise $S_{i_n}(C)$ would be contained in the complement of $T_0$, contradicting finiteness of the set of indices in which $S_i(C)$ is infinite when restricted along the chain of predecessors; thus one can choose $i_{n+1}\in S_{i_n}(C)\cap T_0$.

This ensures that for every $n$, the block $A(i_n,i_{n+1})$ lies in class $C$, and also $i_n\in T_0$, so the construction can continue indefinitely.

Now define the partition of the infinite expansion by taking the first block $A(0,i_1)$ arbitrarily, and all subsequent blocks $A(i_n,i_{n+1})$ for $n\ge 1$. By construction, every block except possibly the first lies in the same class $C$.

This completes the proof.

∎

Verification of Key Steps

The crucial step is the existence of a class $C$ and an infinite set $T_0$ of indices such that every $i\in T_0$ admits infinitely many extensions in class $C$. If this failed for every class, then for each class $C_k$ the set of indices $i$ with infinitely many $C_k$-extensions would be finite, hence their union over finitely many $k$ would be finite. This contradicts that every index $i$ admits at least one class with infinitely many extensions.

The second delicate point is preservation of membership in $T_0$ during the inductive construction. Since each $i_n$ lies in $T_0$, the set $S_{i_n}(C)$ is infinite, and among infinitely many candidates at least one remains in $T_0$, otherwise all sufficiently large indices would fail the defining property of $T_0$, contradicting its infinitude.

The final point is that each block is well-defined as a natural number in decimal form, since every finite digit string corresponds uniquely to a natural number.

Alternative Approaches

A different approach encodes the situation as a finitely branching infinite tree whose nodes are indices and whose edges correspond to possible next cuts labeled by classes. Then one applies an infinite-path argument akin to König’s lemma together with a stabilization argument on edge labels to extract a monochromatic infinite path.

Another viewpoint uses a compactness argument: the space of all infinite partitions into finite blocks is compact in the product topology, and the coloring induces a finitely-valued labeling on edges, allowing extraction of a limit object where the label stabilizes along a tail of the partition.