Problem 8.8. In how many ways can all natural numbers from 1 to 200 be painted in red and blue so that the sum of any two different numbers of the same color is never equal to a power of two?
Answer: 256.

## Solution.

Lemma. If the sum of two natural numbers is a power of two, then the powers of 2 in the prime factorizations of these two numbers are the same.

Proof of the lemma. Let the sum of the numbers $a=2^{\alpha} \cdot a_{1}$ and $b=2^{\beta} \cdot b_{1}$, where $a_{1}$ and $b_{1}$ are odd, be $2^{n}$. Since $2^{n}=a+b>a \geqslant 2^{\alpha}$, then $n>\alpha$. Suppose that $\alpha$ and $\beta$ are different, without loss of generality, $\alpha>\beta$. Then $b=2^{\beta} \cdot b_{1}=2^{n}-2^{\alpha} \cdot a_{1}=2^{\alpha}\left(2^{n-\alpha}-a_{1}\right)$ is divisible by $2^{\alpha}$. But $\beta<\alpha$, a contradiction. The lemma is proved.

We call a two-color coloring of a set $M$ good if the sum of any two different numbers of the same color from the set $M$ is not a power of two. We call a two-color coloring of a sequence $x_{1} \leqslant x_{2} \ldots \leqslant x_{t}$ alternating if any two adjacent numbers in this sequence are painted in different colors.

Consider 8 sets of numbers, each having the same power of 2 in their prime factorization:

$$
M_{0}=\{1,3,5, \ldots, 199\}, M_{1}=\{2,6,10, \ldots, 198\}, M_{2}=\{4,12,20, \ldots, 196\}, \ldots, M_{7}=\{128\}
$$

We will prove that for each of these 8 sets, there exist exactly two good colorings, both of which are alternating. Since numbers from different sets do not add up to a power of two (this follows from the lemma), we will get that the total number of good colorings of the numbers $1,2, \ldots, 200$ is exactly $2^{8}=256$.

Consider $M_{k}=\left\{2^{k}, 3 \cdot 2^{k}, 5 \cdot 2^{k}, \ldots\right\}$. Consider the set of numbers $M_{k}^{*}$, which contains all the numbers of the set $M_{k}$ divided by $2^{k}$. Obviously, any good coloring of the set $M_{k}$ corresponds to exactly one good coloring of the set $M_{k}^{*}$ (if the sum of two numbers was a power of two, then the sum of these numbers divided by $2^{k}$ will also be a power of two, and vice versa). It is sufficient to prove that for $M_{k}^{*}$ there exist exactly two good colorings, both of which are alternating.

Obviously, $M_{k}^{*}$ consists of several of the first odd natural numbers (possibly one). Without loss of generality, the number 1 in it is red. Since $1+3=2^{2}$, the number 3 is blue. Since $5+3=7+1=2^{3}$, the number 5 is red, and the number 7 is blue. This can be continued: if the coloring of the odd numbers from 1 to $2^{s}-1$ is alternating, then the coloring of the odd numbers from $2^{s}+1$ to $2^{s+1}-1$ is also alternating (since $\left.\left(2^{s}+1\right)+\left(2^{s}-1\right)=\left(2^{s}+3\right)+\left(2^{s}-3\right)=\ldots=\left(2^{s+1}-1\right)+1=2^{s+1}\right)$. At the same time, the numbers $2^{s}-1$ and $2^{s}+1$ are painted in different colors, so the coloring of the numbers from 1 to $2^{s+1}-1$ is also alternating. Thus, if the number 1 is red, then the coloring is uniquely determined, and it is alternating. Obviously, if the number 1 is blue, then the coloring is also uniquely determined, and it is also alternating. It is also clear that alternating colorings work: in them, any two different numbers of the same color are odd and have the same remainder when divided by 4, so their sum is greater than 2 and does not divide by 4, hence it is not a power of two. There are no other colorings.

Another solution. If the sum of two different numbers is a power of two, we will call the smaller of them the parent of the larger one. We will prove that powers of two have no parents, and all other numbers have exactly one parent.

Indeed, consider a number $x$ in the range $2^{k-1} \leqslant x<2^{k}$ for some $k \geqslant 0$. Let one of its parents be some number $y<x$. Then $2^{k-1} \leqslant x<$
$x+y<2 x<2^{k+1}$, from which $x+y=2^{k}$ (this must be some power of two). Therefore, the parent $y=2^{k}-x$ for $x \neq 2^{k-1}$ is uniquely determined (and for $x=2^{k-1}$ we get $y=x$, which is impossible). On the other hand, it is clear that if $x \neq 2^{k-1}$, then $2^{k}-x$ is indeed a parent of the number $x\left(2^{k}-x \leqslant 2^{k}-2^{k-1}=2^{k-1}<x\right.$ and $\left.2^{k}-x+x=2^{k}\right)$.

Now we will show that any coloring of the powers of two can be uniquely continued to a coloring of the entire given set of numbers. Suppose all powers of two from our set are already painted red or blue. We will start going through the other numbers in ascending order $(3,5,6, \ldots)$; when we reach the next number, it will have a parent, and it will already be painted. Therefore, we can paint the current number in the only possible way - in the color opposite to the color of its parent. This way we will paint all the numbers.

The resulting coloring will satisfy the condition, since in any pair of numbers that add up to a power of two, the larger number will be painted in the color opposite to the color of its parent, i.e., the smaller number of the pair.

Therefore, the number of ways to color the given range in the required manner coincides with the number of ways to color the powers of two from the range arbitrarily. Since we have 8 powers of two (from $2^{0}$ to $2^{7}$), the number of ways is exactly $2^{8}$.

## 9th grade