EGMO 2024
問題 4

$a_i\lt a_j$ に対して $(a_i,a_j)$ が面白い組であるとき $f_n(a_i,a_j)=1$，そうでないとき $f_n(a_i,a_j)=0$ となる関数 $f$ を考えると求めるべき値は

$$\sum_{1\leq i\lt j \leq n}f(a_i,a_j)$$

の最大値である．$n+1$ のときを考える．一般性を失わず $a_{n+1}-a_1\geq 2(a_{n+1}-a_{\lfloor(n+2)/2\rfloor})$ としてよい．このとき

$$\sum_{1\leq i\lt j \leq n+1}f(a_i,a_j)=\sum_{1\leq i\lt k \leq n}f(a_i,a_j)+\sum_{1\leq i\leq n}f(a_i,a_{n+1})\leq\sum_{1\leq i\lt j \leq n}f(a_i,a_j)+\left\lfloor\dfrac{n+1}{2}\right\rfloor$$

が従うので帰納的に

$$\sum_{1\leq i\lt j \leq n}f(a_i,a_j)\leq \left\lfloor\dfrac{n}{2}\right\rfloor\left\lfloor\dfrac{n+1}{2}\right\rfloor$$

が従う．一方で $a_1,a_2,\ldots,a_n$ が等差数列のときに $\sum_{1\leq i\lt j \leq n}f(a_i,a_j)= \left\lfloor\dfrac{n}{2}\right\rfloor\left\lfloor\dfrac{n+1}{2}\right\rfloor$ が成立するのでこれが求める最大値である．