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$ を考えると求めるべき値は

の最大値である．$n+1$ のときを考える．一般性を失わず $a_{n+1}-a_1\geq 2(a_{n+1}-a_{\lfloor(n+2)/2\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$ が成立するのでこれが求める最大値である．