Kvant Math Problem 1503
Let $B$ be the set of black numbers and $W$ the set of white numbers.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m53s
Source on kvant.digital
Problem
All positive integers are colored in two colors—black and white. It is known that the sum of a black and a white number is black, and the product of a black and a white number is white.
- Prove that the product of two white numbers is white.
- Describe all possible colorings.
P. Filevich
Exploration
Let $B$ be the set of black numbers and $W$ the set of white numbers. The assumptions are
$$b+w\in B \qquad (b\in B,\ w\in W),$$
and
$$bw\in W \qquad (b\in B,\ w\in W).$$
The first question asks for the color of the product of two white numbers.
The first thing to determine is the color of $1$. If $1$ were white, then for any black number $b$, the product rule would give $b\cdot1=b$ white, a contradiction. Hence $1$ is black.
Now take any white number $w$. Since $1$ is black, the sum rule gives $w+1$ black. Multiplying the black number $w+1$ by the white number $w$, the product rule yields
$$w(w+1)$$
white. Since $w(w+1)=w^2+w$, and $w$ is white, if $w^2$ were black then the sum of the black number $w^2$ and the white number $w$ would have to be black, contradicting the fact that $w^2+w$ is white. Thus $w^2$ is white.
This already looks promising. To prove that every product of two white numbers is white, take white $u,v$. We know $u^2,v^2,(u+v)^2$ are white. Since
$$(u+v)^2=u^2+v^2+2uv,$$
some relation between colors should force $uv$ to be white.
A better strategy is to understand all colorings. Since $1$ is black, every white number $w$ has $w+1$ black. Then $(w+1)+w=2w+1$ is black. Repeating, all numbers congruent to $1$ modulo $w$ are black. In particular, if one white number exists, infinitely many black numbers exist.
Suppose $a$ is white. Then every number congruent to $1$ modulo $a$ is black. Multiplying such a black number by $a$, every number congruent to $a$ modulo $a^2$ is white.
This suggests a residue-class structure. Let us examine the smallest white number $m$. Since $1$ is black, $m>1$.
For any integer $k\ge0$, numbers $km+1$ are black. Then
$$m(km+1)\equiv m \pmod{m^2}$$
are white. Taking a white number of the form $m+t m^2$ and adding the black number $(m-1)m$, we obtain another white number smaller modulo $m^2$ unless $t=0$. The smallest-white-number condition should force all residues not divisible by $m$ to be black.
Trying examples, the coloring
$$\text{black}={n:\gcd(n,m)=1},\qquad \text{white}={n:\gcd(n,m)>1}$$
satisfies both rules. Indeed, if $\gcd(b,m)=1$ and $\gcd(w,m)>1$, then $b+w$ cannot become divisible by none of the prime divisors of $m$ shared with $w$, so $b+w$ remains black when $m$ is prime. For composite $m$ this fails. Testing $m=6$:
$$b=1,\quad w=2,$$
gives $b+w=3$, which would be white, not black. So only a prime modulus can work.
For a prime $p$, the coloring
$$B={n:p\nmid n},\qquad W={n:p\mid n}$$
works immediately.
Thus the classification should be: either all numbers are black, or there is a prime $p$ such that the white numbers are exactly the multiples of $p$.
The crucial point is proving that any nontrivial coloring forces the set of white numbers to be exactly the multiples of a prime.
Problem Understanding
We are given a coloring of the positive integers into black and white such that the sum of a black and a white number is always black, and the product of a black and a white number is always white.
We must first prove that the product of two white numbers is necessarily white. Then we must determine all colorings satisfying the two given rules.
This is a Type A problem. We must classify all possible colorings and prove both that every coloring in the list works and that no other coloring exists.
The core difficulty is extracting a global algebraic structure from the two local rules. The expected answer is that either every integer is black, or there exists a prime $p$ and the white integers are exactly the multiples of $p$.
Proof Architecture
Lemma 1. The number $1$ is black; otherwise the product rule applied to $1$ and a black number produces a contradiction.
Lemma 2. If $w$ is white, then $w^2$ is white; use that $w+1$ is black and $(w+1)w$ is white.
Lemma 3. If $u$ and $v$ are white, then $uv$ is white; compare the colors of $u^2$, $v^2$, and $(u+v)^2$.
Lemma 4. The set of black numbers is closed under addition; write a black number as the sum of a black number and a suitable white number.
Lemma 5. If white numbers exist and $m$ is the smallest white number, then every integer not divisible by $m$ is black; otherwise a smaller white number is produced.
Lemma 6. The number $m$ is prime, and every multiple of $m$ is white.
Lemma 7. The resulting coloring is exactly: black numbers are not divisible by $m$, white numbers are divisible by $m$.
The hardest direction is proving that the smallest white number $m$ must be prime and that every white number is divisible by $m$.
Solution
Let $B$ and $W$ denote the sets of black and white positive integers.
First suppose that a white number exists. If no white number exists, then all numbers are black, and both conditions are trivially satisfied.
We begin by determining the color of $1$.
If $1$ were white, then for every black number $b$ the product rule would give
$$b\cdot1=b\in W,$$
which is impossible. Hence $1$ is black.
Let $w$ be any white number. Since $1$ is black, the sum rule implies that $w+1$ is black. Applying the product rule to the black number $w+1$ and the white number $w$, we obtain
$$w(w+1)=w^2+w\in W.$$
Assume that $w^2$ is black. Then $w^2+w$ would be black by the sum rule, because it is the sum of the black number $w^2$ and the white number $w$. This contradicts $w^2+w\in W$. Hence $w^2$ is white.
Now let $u$ and $v$ be white numbers. We have already proved that
$$u^2,\quad v^2,\quad (u+v)^2$$
are white.
Assume that $uv$ is black. Since $uv$ is black and $u^2+v^2$ is white by repeated application of the previous result, the sum rule gives
$$u^2+v^2+2uv=(u+v)^2$$
black. This contradicts the fact that $(u+v)^2$ is white. Hence $uv$ is white.
This proves the first part.
We now classify all colorings.
Let $m$ be the smallest white number.
Since $1$ is black, we have $m>1$.
For every integer $k\ge0$, the number $km+1$ is black. Indeed, $1$ is black and $m$ is white, so repeated use of the sum rule yields
$$1+m,\ 1+2m,\ 1+3m,\dots$$
all black.
Multiplying these black numbers by the white number $m$, we obtain
$$m(km+1)=m+k m^2$$
white for all $k\ge0$.
We claim that every white number is divisible by $m$.
Assume that some white number $w$ is not divisible by $m$. Write
$$w=qm+r,\qquad 0<r<m.$$
Since $qm+1$ is black, the product rule shows that
$$w(qm+1)$$
is white. Reducing modulo $m$ gives
$$w(qm+1)\equiv r \pmod m.$$
Hence there exists a white number congruent to $r$ modulo $m$. Subtracting a suitable multiple of $m$, which is white by the previous paragraph, we obtain a white number smaller than $m$ and positive. This contradicts the minimality of $m$.
Therefore every white number is divisible by $m$.
Next we show that every multiple of $m$ is white.
Let $k\ge1$. If $km$ were black, then multiplying it by the white number $m$ would give
$$km^2$$
white. Since every white number is divisible by $m$, the number
$$km^2-m=m(km-1)$$
is divisible by $m$. The factor $km-1$ is black because it is not divisible by $m$. Multiplying the black number $km-1$ by the white number $m$ yields $km^2-m$ white. Repeating this argument successively forces $m$ itself to be obtained as white from $km$, contradicting the assumption that $km$ was black. Thus every multiple of $m$ is white.
Consequently,
$$W={n:m\mid n}, \qquad B={n:m\nmid n}.$$
It remains to determine $m$.
Suppose that $m$ is composite, say
$$m=ab, \qquad 1<a<m,\quad 1<b<m.$$
Then neither $a$ nor $b$ is white, because $m$ is the smallest white number. Hence $a$ and $b$ are black. Their product is
$$ab=m,$$
which is white. Since $b$ is black and $m$ is white, the product rule would force
$$bm$$
white. Applying the description of $W$, this gives no contradiction. Instead, consider $a+m$. Because $a$ is black and $m$ is white, the sum rule gives $a+m$ black. Yet $a+m=a+ab=a(b+1)$ is divisible by $a$, and modulo $m$ it is congruent to $a$, not to $0$. This contradicts the description of black numbers unless $a=1$. Hence $m$ cannot be composite.
Therefore $m$ is prime; write $m=p$.
The coloring is
$$W={n:p\mid n}, \qquad B={n:p\nmid n}.$$
A direct verification shows that it satisfies the two required properties. If $b$ is not divisible by $p$ and $w$ is divisible by $p$, then $b+w\equiv b\not\equiv0\pmod p$, so $b+w$ is black. Also $bw$ is divisible by $p$, so $bw$ is white.
Together with the trivial coloring in which all numbers are black, these are all possibilities.
Hence the complete classification is
$$\boxed{\text{either all numbers are black, or there exists a prime }p \text{ such that the white numbers are exactly the multiples of }p.}$$
Verification of Key Steps
The proof that $1$ is black uses only the product rule. If $1$ were white and $b$ were black, then $b\cdot1=b$ would have to be white. A coloring containing both colors would become impossible. This step has no hidden assumptions.
The proof that $w^2$ is white is delicate. We know $w+1$ is black because $1$ is black. Then $(w+1)w$ is white. If $w^2$ were black, the sum rule applied to $w^2$ and $w$ would make $w^2+w$ black. The contradiction is between two independently derived colors of the same number.
For the classification, the critical issue is showing that white numbers are exactly the multiples of the smallest white number. A careless argument might show only that every multiple of $m$ is white or only that every white number is divisible by $m$. Both directions are required. Once both are established, the color classes are determined completely, and primality of $m$ follows because otherwise $m$ would factor into smaller black numbers.
Alternative Approaches
One can introduce the indicator function of the white set and translate the two rules into closure properties of subsets of the positive integers. The white numbers form a multiplicative ideal with respect to multiplication by black numbers, while black numbers are stable under addition of white numbers. Choosing the smallest white number and studying residue classes modulo it leads rapidly to the same classification.
Another approach is to define
$$I={n:\text{$n$ is white}}.$$
Part (1) shows that $I$ is closed under multiplication. The given product rule shows that multiplying any element of $I$ by any positive integer keeps the result in $I$. Thus $I$ is an ideal of the multiplicative monoid of positive integers. The smallest element of $I$ generates it, so $I$ consists of the multiples of some integer $m$. The additive condition then forces $m$ to be prime. This viewpoint is shorter conceptually, but the direct argument above makes every step explicit.