Maths Olympiad Prep

Library / /20 of 22

Combinatorics Difficulty 9.1 IMO level Prove it Vietnam

Given a set A={1,2,,4044}A = \{1, 2, \dots, 4044\}. One colors 2022 numbers of them by white and the rest by black. For each iAi \in A, denote the weight of ii by sum of the amount of white numbers that are smaller than ii and the amount of black numbers that are larger than ii. For every positive integer mm, find all positive integers kk such that there exists a way to color the numbers which can get exactly kk numbers having weight mm.

Solution

Call a natural number ii good if its weight is mm. We will prove the following claim.

Claim. Consider a positive integer i4044i \le 4044.

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

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

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

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

Call a natural number ii is 'good' if it has weight mm. We shall prove that kk is an even number. Indeed, let ii be smallest good number and denote aj,bja_j, b_j to be the number of white, black numbers before and after jj. If j<ij < i then
aj+bjai+bi. a_j + b_j \neq a_i + b_i.
If ii is black then the number of white numbers from 11 to i1i - 1 is smaller than the number of black numbers, otherwise, by lemma 1, we can find a black number jj such that in the interval [j+1,i1][j+1, i-1], the numbers of black and white numbers are equal, which means
aiaj=bibj a_i - a_j = b_i - b_j
But jj is also a good number, which means this relation leads to a contradiction. Note that the number of black numbers before ii is 2021b12021 - b_1, hence
m=ai+bi<2022bi+bi=2022. m = a_i + b_i < 2022 - b_i + b_i = 2022.
Next, we will prove that if ss is good and black then there exists s>ss' > s such that ss' is good and white. Because ss is black then the number of white numbers after ss is 2022as2022 - a_s, then
bs=mas<2022as b_s = m - a_s < 2022 - a_s
Applying lemma 1, we get a number s>ss' > s such that ss' is white and the numbers of black and white numbers in [s+1,s1][s+1, s'-1] are equal. Hence,
asas=bsbs a_{s'} - a_s = b_{s'} - b_s
which means ss' is also a good number. Thus, if A={x1<x2<<xk}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 x1x_1 is black so x2t+1x_{2t+1} is black for all tt, which is a contradiction because there must exist k>xkk' > x_k such that kk' is good and white.

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

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

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

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

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

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

* 1,2,,m+1j1, 2, \dots, m+1-j are colored by white.
* m+2j,,2023+m2jm+2-j, \dots, 2023+m-2j are colored by black.
* 2024+m2j,,2024+m2024+m-2j, \dots, 2024+m are colored by black and 2025+m2j,,2023+m2025+m-2j, \dots, 2023+m are colored by white.
* The remaining numbers are colored by white.

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

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

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

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

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

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

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.