Given a set . One colors 2022 numbers of them by white and the rest by black. For each , denote the weight of by sum of the amount of white numbers that are smaller than and the amount of black numbers that are larger than . For every positive integer , find all positive integers such that there exists a way to color the numbers which can get exactly numbers having weight .
Solution
Call a natural number good if its weight is . We will prove the following claim.
Claim. Consider a positive integer .
a. If there are more black numbers than white from to , then there exists a black number such that the numbers of black and white numbers from to are equal.
b. If there are more white numbers than black from to then there exists a white number such that the numbers of black and white numbers from to are equal.
Proof. Clearly (a) and (b) are similar so we only need to prove (b). Denote to be the difference of the numbers of black and white numbers from to . It is clear that and
Now we need to point out that there exists such that is white and . If is white and then we can assume is black, then . Because the number of white numbers from to is more than the black numbers, then . Hence,
We will point out that there exists such that . If there exists the smallest natural number that , note that
so and , hence . Otherwise, if for all then , which means there always exists a number has that property.
Assume that for all that , the number is always black which means . Similarly, if there exists the smallest number such that then , hence for all . Thus, , which means the numbers of black and white numbers from to are equal so is colored by white. Otherwise, if there exists such that and is white then satisfies the above condition.
Back to the problem, assume that are two consecutive good numbers and have the same color white. We observe that there are less white numbers before than and there are less black numbers after than . Hence, the weight of is smaller than the weight of , which is a contradiction. Thus, they must be colored by different colors.
Call a natural number is 'good' if it has weight . We shall prove that is an even number. Indeed, let be smallest good number and denote to be the number of white, black numbers before and after . If then
If is black then the number of white numbers from to is smaller than the number of black numbers, otherwise, by lemma 1, we can find a black number such that in the interval , the numbers of black and white numbers are equal, which means
But is also a good number, which means this relation leads to a contradiction. Note that the number of black numbers before is , hence
Next, we will prove that if is good and black then there exists such that is good and white. Because is black then the number of white numbers after is , then
Applying lemma 1, we get a number such that is white and the numbers of black and white numbers in are equal. Hence,
which means is also a good number. Thus, if is the set of good numbers then two consecutive numbers have different colors by lemma 2. Note that is black so is black for all , which is a contradiction because there must exist such that is good and white.
Similarly, if is white then we can point out that and for any number that is good and white, there exists which is good and black. Thus, is an even number in all cases.
Now, by all of these arguments, we shall prove that
Case 1. If then .
Case 2. If then .
Indeed, denote with is a natural number.
Case 1. Because so the smallest good number is black. Because there are good numbers then there are exactly numbers after that are good and black. Hence, there are at most white numbers before , which means . Thus, and for all and , we color the numbers as follows.
* are colored by white.
* are colored by black.
* are colored by black and are colored by white.
* The remaining numbers are colored by white.
We can check that is good if and only if , thus there are exactly good numbers.
Case 2. Since , there are at least black numbers after the last good number and there are at least white numbers before the first good number. Hence, if is a good number then
or there are at most good numbers. Now if , we color by black and by white. The construction for can be pointed out as follows.
a) The first numbers and the last numbers are colored by black.
b) have alternative colors and is white.
c) have alternative colors and is black.
d) are colored by a same color which is different from .
e) are colored by a same color which is different from .
We can check that if is good then belongs to c) or d) so there are exactly good numbers. The solution is finish.