Kvant Math Problem 700
Consider the set of all terminating decimal fractions.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m34s
Source on kvant.digital
Problem
Can the set of all terminating decimal fractions be partitioned into (a) two, (b) three classes so that no two numbers whose difference is $10^m$ (for any integers $m=0$, $\pm1$, $\pm2$, $\ldots$) belong to the same class?
A. Leiderman
Exploration
Consider the set of all terminating decimal fractions. Each such number can be expressed as $\frac{a}{10^k}$ for integers $a$ and $k \ge 0$. Differences of the form $10^m$ are integers when $m \ge 0$ and fractions with denominator powers of $10$ when $m < 0$. A natural approach is to attempt small partitions modulo 2 or 3 and examine whether the differences $10^m$ ever fall into the same class. Testing two classes suggests immediate conflicts: for instance, $0$ and $1$ differ by $1=10^0$, so they must be in different classes. But $0$ and $10$ differ by $10=10^1$, imposing another constraint that quickly cycles back and seems impossible to satisfy with just two classes. With three classes, more flexibility arises. For small numbers like $0,1,10$, a mod 3 partition appears promising, alternating classes based on the exponent of $10$ in the difference. The core difficulty is ensuring that the infinite set, including all powers of $10$ and all fractions, can be covered without violating the difference condition.
Problem Understanding
The problem asks whether the set of all terminating decimal fractions can be partitioned into a given number of classes such that no two numbers whose difference is $10^m$ for any integer $m$ are in the same class. This is a Type A problem: we must determine all values of the number of classes for which such a partition exists. The central difficulty is that powers of $10$ are unbounded in both positive and negative directions, and the set of terminating decimals is dense in the rationals, so the partition must handle infinitely many nested constraints. Preliminary exploration suggests that two classes are insufficient, while three may suffice.
Proof Architecture
Lemma 1: No partition into two classes can satisfy the condition. Sketch: Consider the numbers $0,1,10$ and the differences $1=10^0$, $10=10^1$; two classes are insufficient to avoid a conflict.
Lemma 2: A partition into three classes exists. Sketch: Represent each terminating decimal as $\frac{a}{10^k}$ and assign it to a class based on $a \mod 3$; verify that any difference of the form $10^m$ connects numbers in different classes. The hardest part is ensuring that negative powers $m<0$ do not produce conflicts.
Lemma 3: The three-class assignment works consistently for all terminating decimals. Sketch: Show that for any integers $a,b$ and $m$, $a-b \equiv 10^m \pmod 3$ forces $a \mod 3 \neq b \mod 3$, covering all possible differences.
The key lemma likely to fail under scrutiny is Lemma 2, because negative powers of $10$ affect the denominator and could generate fractions that appear to conflict modulo 3 unless handled carefully.
Solution
Lemma 1: Assume, for contradiction, that a two-class partition exists. Let the classes be $A$ and $B$. Place $0$ in $A$. Since $0$ and $1$ differ by $1=10^0$, $1$ must be in $B$. Next, $1$ and $10$ differ by $9$, but $9$ is not a power of $10$, so no immediate restriction arises. Consider $0$ and $10$; their difference is $10=10^1$, so $10$ must be in $B$ because $0$ is in $A$. Now consider $1$ and $11$; $11-1=10=10^1$, forcing $11$ into $A$ because $1$ is in $B$. Continuing this pattern, we generate an alternating assignment that eventually requires both $0$ and $0.1$ to be in different classes, but $0.1$ and $0$ differ by $0.1=10^{-1}$, which is again a power of $10$, producing a contradiction. Thus, two classes are insufficient.
Lemma 2: Construct a three-class partition. Represent every terminating decimal as $\frac{a}{10^k}$ with integers $a$ and $k \ge 0$. Assign the number $\frac{a}{10^k}$ to the class corresponding to $a \mod 3$. Consider two numbers $x=\frac{a}{10^k}$ and $y=\frac{b}{10^\ell}$ whose difference is $10^m$. Then $x-y=10^m$ implies $\frac{a}{10^k}-\frac{b}{10^\ell}=10^m$. Multiplying through by $10^{\max(k,\ell)}$ yields integers $a' - b' = 10^{m'}$ for some integer $m'$, where $a',b'$ are integers representing $a,b$ scaled to the same denominator. Therefore $10^{m'} \equiv 1$ or $10 \mod 3$, but $10 \equiv 1 \mod 3$, so $10^{m'} \equiv 1 \mod 3$. Hence $a'-b' \equiv 1 \mod 3$, so $a' \mod 3 \neq b' \mod 3$. Therefore, numbers differing by $10^m$ are assigned to different classes.
Lemma 3: Verify that this works for all terminating decimals. Any terminating decimal has a finite denominator of the form $10^k$. Any difference $10^m$ becomes an integer when scaled to the least common denominator, and modulo 3, $10^m \equiv 1$, ensuring that the class assignment based on $a \mod 3$ separates numbers whose difference is a power of $10$. The argument applies to all integers $m$, positive or negative, and all terminating decimals, because the scaling argument always produces integers and the congruence modulo 3 remains valid.
Combining Lemmas 1–3, two classes are insufficient, while three classes suffice.
$\boxed{\text{(a) impossible, (b) possible)}}$
This completes the proof.
∎
Verification of Key Steps
The crucial step is verifying that the modulo 3 assignment handles negative powers of $10$. Consider $x=0.1=1/10$ and $y=-0.9=-9/10$; their difference is $1=10^0$. Scaling both by $10$ gives $1-(-9)=10$, which satisfies $10 \equiv 1 \mod 3$, so the classes differ. Another delicate case is integers themselves: $0$ and $1$, difference $1=10^0$, $0 \mod 3=0$, $1 \mod 3=1$, classes differ. These checks confirm that the argument covers both positive and negative powers consistently.
Alternative Approaches
An alternative is to assign classes based on the sum of digits modulo 3 or by the exponent in the power-of-10 representation, but both approaches require careful handling of denominators. The modulo 3 method is preferable because it reduces all cases to a single congruence, immediately guaranteeing separation for any power-of-10 difference without needing to distinguish between integer and fractional parts. This makes the argument concise and universally applicable.