Given a set $A=\{1;2;...;4044\}$. They color $2022$ numbers of them by white and the rest of them by black. With each $i\in A$, called the important number of $i$ be the number of all white numbers smaller than $i$ and black numbers larger than $i$. With every natural number $m$, find all positive integers $k$ that exist a way to color the numbers that can get $k$ important numbers equal to $m$.
Problem
Source: Vietnam TST 2022 P6
Tags: set theory, important numbers, colorings, combinatorics
CANBANKAN
18.06.2022 06:02
continuity
Let $N=2022$. For each $0\le k\le 2N-1$ the number of numbers with weight $k$ can be an even number from $0$ to $2\min\{k+1, 2N-k\}$. Let $c_i=1$ if the number $i$ is colored black, and $c_i=-1$ otherwise. This means $c_1+\cdots+c_{2N}=0$
Then the number of white numbers among the first $t-1$ is $$\frac{(t-1)-(c_1+\cdots+c_{t-1})}{2}$$
The number of black numbers among the last $2N-t$ is $$\frac{c_{t+1}+\cdots+c_{2N} + 2N-t}{2}$$
Their sum is also the weight of $t$. This is equal to $f(t)=frac{2N-1}{2}-\frac 12(c_1+\cdots+c_{t-1}+c_1+\cdots+c_t)=\frac{2N-1-c_t}{2}-c_1-\cdots-c_{t-1}$
Claim: for a fixed $k$, the number of solutions to $f(t)=k$ is even. In fact, when the solutions are written in ascending order, the colors alternate between black and white.
Proof: let $d_j=\frac{c_j+c_{j-1}}{2}= f(j-1)-f(j)$
Suppose $f(t)=f(u)=k$ and $c_t=c_u=1$. Then I claim there exists $v$ such that $t<v<u, c_v=-1$ and $f(v)=k$
If $c_{u-1}=-1$ then $u-1$ satisfies the criteria, so we'll only deal with the case where $c_{u-1}=c_{t+1}=1, f(t+1)=k-1, f(u-1)=k+1$
Observe $d_j\in \{-1,0,1\}$, so $f$ is discrete continuous. Thus, there exists $v$ such that $f(v)>f(v-1)$, $f(v)=k$, which implies $d_v=-1, c_v=c_{v-1}=-1$.
It remains to show that the leftmost and rightmost solutions to $f(t)=k$ have different colors. Observe the following:
$f(1)=\frac{2N-1-c_1}{2}, f(n)=\frac{2N-1+c_n}{2}$. Therefore, by discrete continuity, if $k\le N-1$ then the smallest solution to $f(t)=k$ is black and largest number is white, and if $k\ge N$ then the smallest solution is white while the largest is black.
We will deal with the case $0\le k\le N-1$, since we can use the conclusion for $k$ to deal with $2N-1-k$ by reversing all colors.
There are at most $k+1$ solutions to $f(t)=k$ where $t$ is white. To see this, if I sort the white numbers as $w_1<\cdots<w_N$ then only $w_1, \cdots, w_{k+1}$ can qualify, since all other numbers have at least $k+1$ white numbers to its left. Similarly, there are at most $k+1$ solutions to $f(t)=k$ where $t$ is black.
Now we construct for weight $0\le k\le N-1$ with $0\le \frac m2 \le k+1$ solutions.
For $m=0$ we use the construction $c_j=(-1)^j$ which makes sure all numbers have weight $N$.
Otherwise, $c_1=\cdots=c_{N-(k+1)}=1$, then $c_{N-k-1+t}=(-1)^{t+1}$ for $1\le t\le m$, then color the next $N-\frac m2$ numbers white, then color the final remaining numbers black. Check this works.