Let $m,n$ be two positive integers with $m \ge n \ge 2022$. Let $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$ be $2n$ real numbers. Prove that the numbers of ordered pairs $(i,j) ~(1 \le i,j \le n)$ such that \[ |a_i+b_j-ij| \le m \]does not exceed $3n\sqrt{m \log n}$.
Problem
Source: 2022 China TST, Test 2, P6
Tags: algebra, combinatorics
16.04.2022 17:16
does anyone have any ideas?
28.04.2022 05:19
Consider a bipartite graph $(U,V)$ with vertices $( \{u_1,\cdots,u_n\}, \{v_1,\cdots,v_n\})$ such that there is an edge between $u_i$ and $v_j$ if $|a_i+b_j-ij|\le m$. Let $E$ be the total number of edges, and $X$ be the number of 2-step walks $v_i\leftrightarrow u_j\leftrightarrow v_k$. Note $i<k$ On one hand, $X=\sum\limits_{j=1}^n \binom{deg(u_j)}{2} \ge n\binom{\frac En}{2}$ by convexity, since $\sum deg(u_j)=E$ On the other hand, for each $i<k, j<l$ such that $(k-i)(l-j)\ge 4m$, the four equations $|a_j+b_i-ji|\le m$ (1), $|a_j+b_k-kj|\le m$ (2), $|a_l+b_i-li|\le m$ (3), $|a_l+b_k-lk|\le m$ (4) cannot simultaneously hold. To see this, (1)+(4) gives $a_j+a_l+b_i+b_k-ji-lk\ge -2m$ or $a_j+a_l+b_i+b_k\ge ji+lk-2m$ On the other hand, (2)+(3) gives $a_j+a_l+b_i+b_k\le jk+li+2m$ Thus, $jk+li+2m \ge ji+lk-2m \leftrightarrow 4m\ge ji+lk-jk-li = (k-i)(l-j)$, absurd. Therefore, there are at most $\frac{4m}{k-i}$ common neighbours of $v_k$ and $v_i$ Fix $d=k-i$, we have $n-d$ pairs $(b_k,b_i)$ and at most $\frac{4m}{d}$ possible values for $d$. Summing this for all $d$: $X\le \sum_d (n-d)\frac{4m}{d} \le 4mn \sum_d \frac 1d \le 4mn (\log n+1)$ Therefore, $\binom{\frac En}{2} \le \frac{4mn(\log n+1)}{n}=4m(\log n+1)$ $\frac En \le \sqrt{8m (\log n+1)}$ Since $n\ge 2022$ and $\sqrt{8}<3$, $E\le 3n \sqrt{m \log n}$. Remarks: This problem is an excellent test of number sense. The two ideas are: 1. When I see sqrt, I try to count number of pairs to get rid of a sqrt. 2. The only way to link $log (n)$ is through harmonic series, which must play out in some way. If you see any one of the two ideas, you are pretty close to a solution. I actually started out with the second idea, thought of a graph interpretation, and then decided to focus on pairs.
28.04.2022 10:13
Actually the original version is $3n\cdot\sqrt{m\ln n}.$ I don't know if you see $\log n\equiv \ln n$ in default? Here I'll present the official solution, somewhat similar to CBK's.
26.11.2022 16:44
Wow this test is really easy... Problem 4 took me around 30 minutes, 5 took me around 1 hour, and I solved problem 6 in 30 minutes while watching the world cup (hope one day China can have some decent matches in the world cup as in IMO lol). Turns out I came up with the exact same proof as the official solution. What I would like to point out is that because $m\geq n$, the number $3n\sqrt{m\ln n}$ is at least $3n^{3/2}$, which is already much bigger than the upper bound of the number of edges in a bipartite graph which has $n$ vertices in each set ($2n$ in total) that has no cycle of the length $4$. From here after some observation I quickly got the lemma we need to wrap up the proof. In my opinion really not a difficult problem.
24.03.2024 19:59
China TST/2/2/3 wrote: Let $m,n$ be two positive integers with $m \ge n \ge 2022$. Let $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$ be $2n$ real numbers. Prove that the numbers of ordered pairs $(i,j) ~(1 \le i,j \le n)$ such that \[ |a_i+b_j-ij| \le m \]does not exceed $3n\sqrt{m \log n}$. Consider the bipartite graph $\mathcal{G}(a_i,b_i)$ , where we join two vertices iff $|a_i + b_j - ij| \leq m$, Let $E$ denote the total number of edges in the graph, let $\mathcal{F}$ denote the number of walks of length $2$ in the graph ($a_i\rightarrow b_j \rightarrow a_k$), evidently by jensen we have $\mathcal{F}=\sum \binom{d_i}{2} \geq n \binom{\frac{E}{n}}{2}$. Claim 1: There are no 4-cycles $a_i \rightarrow b_j \rightarrow a_k \rightarrow b_l \rightarrow a_i$ such that $(k-i)(j-l) \geq 4m$.
By Claim 1, for any two $a_i,a_j$ they have at most $\frac{4m}{j-k}$ possible common neighbours, summing this up and using jensen yields the desired inequality. $\blacksquare$
10.05.2024 18:21
If I want to use Bipartite Graph,what can I do?