Exercise 8. A coloring of the integers $\{1,2, \cdots, 2020\}$ in blue and red is said to be pleasant if there do not exist two distinct integers in $\{1,2, \cdots, 2020\}$ of the same color whose sum is a power of 2. How many such colorings exist?
Solution to Exercise 8: A first idea is to test the statement for smaller values, for example for a coloring of the integers from 1 to 7.

Let's color the numbers in order: to color 1, there is no apparent constraint, the same for coloring 2. However, since $3+1=4$, the color of 3 is imposed. To color 4, there is no apparent constraint because $4+3=7, 4+2=6$, and $4+1=5$ are not powers of two. However, since $5+3=6+2=7+1=8$, the color of 5, 6, and 7 is imposed. By testing all possible colorings, we see that regardless of the colors chosen to color 1, 2, and 4, the resulting coloring is pleasant. We can therefore assume that a pleasant coloring is fixed once the colors of the powers of 2 are chosen and that any coloring of the powers of 2 can be extended to a pleasant coloring.

We will show that for any coloring of the powers of 2 between 1 and 2020, there exists a unique way to color the other numbers to obtain a pleasant coloring.

To do this, we will proceed by induction. Let's show that if we color the powers of 2 from 1 to $\mathrm{N}$, then there is a unique pleasant way to color the other integers from 1 to $\mathrm{N}$.

The result is clear for $\mathrm{N}=1$.

Let $\mathrm{N}$ be such that the result is true for $\mathrm{N}-1$. We color the powers of 2 from 1 to $\mathrm{N}$. By the induction hypothesis, there is a unique pleasant way to color the other integers from 1 to $\mathrm{N}-1$.

If $\mathrm{N}=2^{\mathrm{k}}$ for some integer $\mathrm{k}$, then $\mathrm{N}$ is already colored and the coloring is pleasant: indeed, if $1 \leqslant \ell<2^{k}$, then $2^{k}+\ell$ is not a power of 2 because $2^{k}<2^{k}+\ell<2^{k+1}$. Thus, in this case, there is a unique way to complete the coloring.

If $\mathrm{N}$ is not a power of 2, then $\mathrm{N}=2^{k}+\mathrm{n}$ with $1 \leqslant \mathrm{n}<2^{k}$ and $k$ an integer. Then $\mathrm{N}$ cannot be colored the same color as $2^{k}-n$ because $N+2^{k}-n=2^{k+1}$. We therefore color $\mathrm{N}$ the other color, and this is indeed the unique way to complete the coloring in a pleasant manner. The resulting coloring is pleasant: indeed, let $\mathrm{t}$ be an integer such that $1 \leqslant \mathrm{t}<\mathrm{N}$ and $\mathrm{t}+\mathrm{N}$ is a power of 2, we have $2^{\mathrm{k}}<\mathrm{N} \leqslant \mathrm{t}+\mathrm{N}<2 \mathrm{~N}=2^{\mathrm{k}+1}+2 \mathrm{n}<2^{\mathrm{k}+1}+2^{\mathrm{k}+1}=2^{\mathrm{k}+2}$, so $\mathrm{t}+\mathrm{N}=2^{\mathrm{k}+1}$. Therefore, $\mathrm{t}=2^{\mathrm{k}+1}-2^{\mathrm{k}}-\mathrm{n}=2^{\mathrm{k}}-\mathrm{n}$. Since we have colored $\mathrm{N}$ and $2^{\mathrm{k}}-\mathrm{n}$ with different colors, the coloring is pleasant.

There are 11 powers of 2 between 1 and 2020, which are $1=2^{0}, 2=2^{1}, \cdots, 1024=2^{10}$, and there are $2^{11}$ ways to color them in blue and red. Thus, there are $2^{11}$ pleasant colorings.

Comment from the graders:

Most students recognized the importance of the powers of 2. Some proposed alternatively to look at elements congruent to $2^{n}$ modulo $2^{\mathrm{n}+1}$, which also worked. Many proved that there were at most 2048 colorings, but very few verified that the colorings thus produced were valid, which was a crucial part of the exercise. It is important to detail the arguments used: for example, using induction is a good idea when you want to generalize something.