IMO Team Selection Test

Call a natural number $i$ good if its weight is $m$. We will prove the following claim.

Claim. Consider a positive integer $i \le 4044$.

a. If there are more black numbers than white from $1$ to $i-1$, then there exists a black number $j$ such that the numbers of black and white numbers from $j+1$ to $i-1$ are equal.

b. If there are more white numbers than black from $i+1$ to $4044$ then there exists a white number $j$ such that the numbers of black and white numbers from $i+1$ to $j-1$ are equal.

Proof. Clearly (a) and (b) are similar so we only need to prove (b). Denote $f(k)$ to be the difference of the numbers of black and white numbers from $i+1$ to $i+k-1$. It is clear that $f(0) = 0$ and
$$|f(x) - f(x + 1)| = 1.$$
Now we need to point out that there exists $k$ such that $i+k$ is white and $f(k) = 0$. If $i+1$ is white and $f(1) = 0$ then we can assume $i+1$ is black, then $f(2) = 1 > 0$. Because the number of white numbers from $i+1$ to $4044$ is more than the black numbers, then $f(4044 - i) \le 0$. Hence,
$$f(2) = 1 > 0 \ge f(4044 - i).$$
We will point out that there exists $j$ such that $f(j) = 0$. If there exists the smallest natural number $t$ that $f(t) < 0$, note that
$$|f(t - 1) - f(t)| = 1$$
so $f(t - 1) = f(t) + 1$ and $f(t - 1) \ge 0$, hence $f(t - 1) = 0$. Otherwise, if $f(t) \ge 0$ for all $t$ then $f(4044 - i) = 0$, which means there always exists a number $j$ has that property.
Assume that for all $j$ that $f(j) = 0$, the number $j+1$ is always black which means $f(j + 1) = 1$. Similarly, if there exists the smallest number $t$ such that $f(t) < 0$ then $f(t - 1) = 0$, hence $f(t) \ge 0$ for all $t$. Thus, $f(4044 - i) = 0$, which means the numbers of black and white numbers from $i+1$ to $4043$ are equal so $4044$ is colored by white. Otherwise, if there exists $j$ such that $f(j) = 0$ and $j+i$ is white then $j$ satisfies the above condition. $\square$

Back to the problem, assume that $i < i'$ are two consecutive good numbers and have the same color white. We observe that there are less white numbers before $i'$ than $i$ and there are less black numbers after $i'$ than $i$. Hence, the weight of $i'$ is smaller than the weight of $i$, which is a contradiction. Thus, they must be colored by different colors.

Call a natural number $i$ is 'good' if it has weight $m$. We shall prove that $k$ is an even number. Indeed, let $i$ be smallest good number and denote $a_j, b_j$ to be the number of white, black numbers before and after $j$. If $j < i$ then
$$a_j + b_j \neq a_i + b_i.$$
If $i$ is black then the number of white numbers from $1$ to $i - 1$ is smaller than the number of black numbers, otherwise, by lemma 1, we can find a black number $j$ such that in the interval $[j+1, i-1]$, the numbers of black and white numbers are equal, which means
$$a_i - a_j = b_i - b_j$$
But $j$ is also a good number, which means this relation leads to a contradiction. Note that the number of black numbers before $i$ is $2021 - b_1$, hence
$$m = a_i + b_i < 2022 - b_i + b_i = 2022.$$
Next, we will prove that if $s$ is good and black then there exists $s' > s$ such that $s'$ is good and white. Because $s$ is black then the number of white numbers after $s$ is $2022 - a_s$, then
$$b_s = m - a_s < 2022 - a_s$$
Applying lemma 1, we get a number $s' > s$ such that $s'$ is white and the numbers of black and white numbers in $[s+1, s'-1]$ are equal. Hence,
$$a_{s'} - a_s = b_{s'} - b_s$$
which means $s'$ is also a good number. Thus, if $A = \{x_1 < x_2 < \dots < x_k\}$ is the set of good numbers then two consecutive numbers have different colors by lemma 2. Note that $x_1$ is black so $x_{2t+1}$ is black for all $t$, which is a contradiction because there must exist $k' > x_k$ such that $k'$ is good and white.

Similarly, if $i$ is white then we can point out that $m \ge 2022$ and for any number $s$ that is good and white, there exists $s' > s$ which is good and black. Thus, $k$ is an even number in all cases.

Now, by all of these arguments, we shall prove that

Case 1. If $m < 2022$ then $k \in \{0, 2, \dots, 2(m+1)\}$.

Case 2. If $m \ge 2022$ then $k \in \{0, 2, \dots, 2(4044 - m)\}$.

Indeed, denote $k = 2j$ with $j$ is a natural number.

Case 1. Because $m < 2022$ so the smallest good number $i$ is black. Because there are $k$ good numbers then there are exactly $j-1$ numbers after $i$ that are good and black. Hence, there are at most $m-j+1$ white numbers before $i$, which means $m \ge j-1$. Thus, $k \le 2(m+1)$ and for all $m < 2022$ and $k = 2j \le 2(m+1)$, we color the numbers as follows.

* $1, 2, \dots, m+1-j$ are colored by white.
* $m+2-j, \dots, 2023+m-2j$ are colored by black.
* $2024+m-2j, \dots, 2024+m$ are colored by black and $2025+m-2j, \dots, 2023+m$ are colored by white.
* The remaining numbers are colored by white.

We can check that $i$ is good if and only if $i \in \{2024 + m - 2j, \dots, 2023 + m\}$, thus there are exactly $2j$ good numbers.

Case 2. Since $m \ge 2022$, there are at least $m - 2022$ black numbers after the last good number and there are at least $m - 2022$ white numbers before the first good number. Hence, if $i$ is a good number then
$$m - 2022 < m < 4044 - (m - 2022)$$
or there are at most $4044 - (m-2022) - (m-2022) = 2(4044-m)$ good numbers. Now if $j = 0$, we color $1, 2, \dots, 2022$ by black and $2023, 2024, \dots, 4044$ by white. The construction for $j > 0$ can be pointed out as follows.

a) The first $m-2022$ numbers and the last $m-2022$ numbers are colored by black.

b) $m-2022+1, \dots, m-2022+j$ have alternative colors and $m-2022+1$ is white.

c) $4044 - (m - 2022) - 1, \dots, 4044 - (m - 2022) - j$ have alternative colors and $4044 - (m - 2022) - 1$ is black.

d) $m-2022+j+1, \dots, 2022$ are colored by a same color which is different from $m-2022+j$.

e) $4044 - (m - 2022) - j - 1, \dots, 2023$ are colored by a same color which is different from $4044 - (m - 2022) - j$.

We can check that if $i$ is good then $i$ belongs to c) or d) so there are exactly $2j$ good numbers. The solution is finish. $\square$