Let $n>100$ be an integer. The numbers $1,2 \ldots, 4n$ are split into $n$ groups of $4$. Prove that there are at least $\frac{(n-6)^2}{2}$ quadruples $(a, b, c, d)$ such that they are all in different groups, $a<b<c<d$ and $c-b \leq |ad-bc|\leq d-a$.
Problem
Source: Kazakhstan National MO 2023 (10-11).2
Tags: algebra
12.04.2023 21:01
Any solution?
17.01.2024 03:50
any solution?
06.02.2024 11:43
Observe that for natural numbers $a,b$ with $a+2\leq b$, we have\[b-(a+1)<|a(b+1)-(a+1)b|<(b+1)-a.\]It suffices to show that there are at least $\frac{(n-6)^2}2$ pairs $(a,b)$ with the four numbers $a$, $a+1$, $b$, $b+1$ in separate groups. Assume the groups are numbered. Let there be $k$ pairs of consecutive numbers that are located in different groups, and of the numbers that are in at least 1 such pair, $k_1$ are in the first group, $k_2$ in the second, and so on (We have $\sum_{i=1}^n k_i\leq2k$). Now since there are $4n-1$ pairs of consecutive integers, and at most $3$ in each group, then $k\geq n-1$. Notice that the number of pairs $(a,b)$ with the four numbers $a$, $a+1$, $b$, $b+1$ in separate groups is at least \[{k\choose2}-\left(\sum_{i=1}^n{{k_i\choose2}+k_i}\right)\geq \frac{k(k-3)}2-\sum_{i=1}^n{k_i\choose2}.\]If $k\geq n+2$, then we have\[\frac{k(k-3)}2-\sum_{i=1}^n{k_i\choose2}\geq \frac{(n+2)(n-1)}2-n\cdot{4\choose2}>\frac{(n-6)^2}2\text{ for all }n>100.\]Now if $n-1\leq k\leq n+1$, notice that ${p\choose2}+{q\choose2}+{r\choose2}+{s\choose2}\leq{4\choose2}$ for non-negative integers $p,q,r,s$ with $p+q+r+s=4$. So, we have \begin{align*}\sum_{i=1}^n{k_i\choose2}&\leq{4\choose2}\cdot\left\lceil\frac{2k}4\right\rceil\leq {4\choose2}\cdot\left\lceil\frac{n+1}2\right\rceil\leq 3(n+2)\\\implies\frac{k(k-3)}2-\sum_{i=1}^n{k_i\choose2}&\geq \frac{(n-1)(n-4)}2-3(n+2)>\frac{(n-6)^2}2\text{ for all } n>100,\end{align*}as required.