Kvant Math Problem 60
The numbers under consideration are exactly the positive integers whose decimal expansion consists only of zeros and ones.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m16s
Source on kvant.digital
Problem
Consider all natural numbers whose decimal representation contains only the digits 1 and 0. Divide these numbers into two groups so that the sum of any two distinct numbers from the same group contains at least two ones in its decimal representation.
E. B. Dynkin, S. A. Molchanov, A. L. Rozenthal, A. K. Tolpygo
Mathematical Problems. 3rd ed. – Moscow: Nauka, 1971.
Exploration
The numbers under consideration are exactly the positive integers whose decimal expansion consists only of zeros and ones. We must partition this infinite set into two classes so that whenever two distinct numbers lie in the same class, their sum contains at least two digits equal to $1$.
The forbidden situation is that the sum of two distinct numbers has at most one digit $1$. Since the numbers are positive, the sum cannot contain no $1$'s. Thus the only forbidden sums are numbers of the form
$$10^m.$$
Indeed, any decimal number with exactly one digit $1$ and all other digits $0$ is a power of $10$.
Let us ask when two distinct $0$-$1$ numbers can add to $10^m$. For small values:
$$1+9=10,$$
but $9$ is not allowed. For
$$10=10,$$
there is no decomposition into two positive $0$-$1$ numbers. For
$$100,$$
we have
$$1+99,$$
again impossible. For
$$1000,$$
the decomposition
$$1+999$$
appears.
This suggests that perhaps no two allowed numbers ever sum to a power of $10$. That would make the problem trivial, so this must be checked carefully.
Take
$$100+900=1000.$$
Again $900$ is not allowed. Try to build a decomposition digit by digit. Since the result has zeros in all positions below the leading one, every lower digit must either be $0+0$ or $1+9$ or involve a carry. Because only digits $0$ and $1$ are available, carries become essential.
Consider
$$111+889=1000,$$
still impossible. Let us write the addition from right to left. To obtain the final leading $1$, there must be a carry into the highest position. Since allowed digits are at most $1$, every lower column producing a carry must have digits $1$ and $1$ together with an incoming carry. This suggests a chain of carries.
Trying examples gives
$$1+111=112,\qquad 10+11=21,\qquad 100+110=210.$$
All have at least two ones.
A better viewpoint is graph theoretic. Let vertices be all $0$-$1$ numbers. Join two vertices when their sum has exactly one digit $1$, equivalently when the sum is a power of $10$. Then the problem asks whether this graph is bipartite. If there are no edges at all, any partition works. We must determine the actual structure.
Suppose
$$a+b=10^m.$$
Let the units digits of $a,b$ be considered. Since $10^m$ ends in $0$, the units column must produce digit $0$. The possibilities with digits $0,1$ are:
$$0+0=0,\qquad 1+1=2.$$
The second gives digit $2$, not $0$. Therefore the units digits are both $0$. Moving to the tens column, there is no carry, so again both digits must be $0$. Continuing inductively, every digit below the highest position is $0$ in both numbers. Hence both numbers are multiples of $10^{m}$, impossible because their sum equals $10^m$.
Thus there are indeed no edges. The condition is automatically satisfied for every pair of distinct allowed numbers.
The only potentially dangerous step is proving rigorously that two such numbers cannot sum to a power of $10$.
Problem Understanding
We consider the set of all positive integers whose decimal digits are only $0$ and $1$. We must divide this set into two groups so that the sum of any two distinct numbers belonging to the same group has at least two digits equal to $1$ in its decimal representation.
This is a Type D problem. We must construct a partition into two groups and verify the required property.
The central difficulty is to understand whether there exist pairs of such numbers whose sum contains fewer than two digits $1$. Since a positive integer with fewer than two digits $1$ has exactly one digit $1$, such a sum would have to be a power of $10$. The key question is therefore whether two distinct $0$-$1$ numbers can sum to a power of $10$.
The answer is that this never happens. Consequently, any partition into two groups works.
Proof Architecture
The first lemma states that a positive integer contains fewer than two digits equal to $1$ if and only if it is a power of $10$; this follows because a positive decimal number with exactly one digit $1$ and all other digits $0$ is precisely $10^m$.
The second lemma states that no two positive integers whose decimal digits are only $0$ and $1$ can have sum equal to a power of $10$; this is proved by examining the decimal addition column by column from the units place upward.
The construction is to place all numbers in one group and leave the second group empty; by the second lemma, every sum of two distinct numbers in the nonempty group contains at least two digits equal to $1$.
The hardest point is the second lemma, because one must rule out all possible carry patterns.
Solution
Let $S$ be the set of all positive integers whose decimal representation contains only the digits $0$ and $1$.
A positive integer contains fewer than two digits equal to $1$ precisely when it contains exactly one digit equal to $1$. Such numbers are exactly the powers of $10$:
$$1,10,100,1000,\dots.$$
Hence the required condition is equivalent to the following statement:
For any two distinct numbers from the same group, their sum is not a power of $10$.
We prove a stronger fact.
Assume that $a,b\in S$ and
$$a+b=10^m$$
for some $m\ge 0$.
Consider the units column of the decimal addition. Since $10^m$ ends in the digit $0$, the units digit of $a+b$ is $0$.
The units digits of $a$ and $b$ are each either $0$ or $1$. Because there is no incoming carry into the units column, the only way to obtain digit $0$ is
$$0+0=0.$$
Therefore the units digits of both $a$ and $b$ are $0$, and no carry is produced.
Now consider the tens column. There is no incoming carry. The tens digit of $10^m$ is also $0$ unless $m=1$, in which case the argument stops here and already shows that both numbers are divisible by $10$, impossible because their sum is $10$.
For $m\ge2$, the tens digit of the sum is $0$. Again the only possibility is
$$0+0=0.$$
Thus the tens digits of both numbers are $0$, and again no carry is produced.
Repeating the same argument successively for every column below the $10^m$ place, we obtain that every digit of $a$ and $b$ in those positions is $0$. Consequently,
$$a\equiv b\equiv 0 \pmod{10^m}.$$
Since $a$ and $b$ are positive integers,
$$a+b\ge 2\cdot10^m,$$
which contradicts
$$a+b=10^m.$$
This contradiction shows that no two numbers from $S$ can have sum equal to a power of $10$.
Therefore the sum of any two distinct elements of $S$ contains at least two digits equal to $1$.
We may now place every element of $S$ into the first group and leave the second group empty. Then any two distinct numbers in the first group satisfy the required condition, and the second group contains no pair of numbers at all.
Thus a valid partition is
$$\boxed{\text{Group 1 }=S,\qquad \text{Group 2 }=\varnothing.}$$
Verification of Key Steps
The crucial step is the analysis of a hypothetical equality
$$a+b=10^m.$$
In the units column there is no incoming carry. With available digits only $0$ and $1$, the sums are $0$, $1$, and $2$. The digit $0$ can occur only from $0+0$. Hence both units digits must be $0$, and no carry is generated. A careless argument might overlook the need to exclude the possibility that a carry from the right produces the digit $0$, but no column lies to the right of the units column.
The induction through the remaining columns depends on the absence of a carry from the previous column. Since each preceding column was forced to be $0+0$, no carry is ever created. Thus every lower digit of both numbers is $0$. Forgetting to prove the persistence of the zero carry would leave a gap.
After establishing divisibility by $10^m$, positivity is essential. From
$$a\equiv b\equiv0\pmod{10^m}$$
and $a,b>0$, one gets
$$a\ge10^m,\qquad b\ge10^m,$$
hence
$$a+b\ge2\cdot10^m.$$
Without using positivity, the contradiction would not follow.
Alternative Approaches
One may formulate the problem as a graph-coloring question. Let the vertices be all $0$-$1$ numbers, and connect two vertices when their sum contains fewer than two digits equal to $1$. Such a sum must be a power of $10$. The preceding argument shows that no edge exists in the graph. A graph without edges is trivially bipartite, so any two-coloring of the vertex set yields a valid partition.
Another approach uses congruences. If $a+b=10^m$, then reducing modulo $10$ gives that both units digits are $0$. Dividing by $10$ and repeating yields that both numbers are divisible by $10^m$. Positivity then contradicts $a+b=10^m$. This is essentially the same idea compressed into a recursive divisibility argument. The column-by-column proof is preferable because it makes the carry mechanism completely explicit.