21-я Международная Жаутыковская олимпиада по математике, 2025 год

Для целого $n>1$ обозначим через $S_n$ множество всех перестановок чисел $1,2,\dots,n$, то есть множество всех взаимно однозначных отображений $\sigma\colon \{1,2,\dots,n\}\to\{1,2,\dots,n\}$. Пару целых чисел $(a,b)$, где $1\leqslant a < b\leqslant n$, назовём {\it расширяющейся} для перестановки $\sigma\in S_n$, если $|\sigma(a)-\sigma(b)|\geqslant |a-b|$.
   (а) Верно ли, что при любом целом $n > 1$ найдется перестановка $\sigma\in S_n$, для которой количество расширяющихся пар меньше, чем $1000n\sqrt n$?
   (б) Существуют ли целое $n>1$ и перестановка $\sigma\in S_n$ такие, что количество расширяющихся пар для $\sigma$ меньше, чем ${1\over 1000}n\sqrt n$? ( И. Богданов )