39-я Международная Математическая OлимпиадаТайвань, Тайбэй, 1998 год

На соревновании выступили $a$ участников, их оценивали $b$ судей, где $b$ — нечетное число, не меньшее 3. За выступление участника каждый судья ставил оценку «удовлетворительно» или «неудовлетворительно». Число $k$ таково, что для любых двух судей имеется не более $k$ участников, получивших у них одинаковые оценки. Докажите неравенство $\dfrac{k}{a}\ge \dfrac{b-1}{2b}$.

Комментарий/решение

Посчитаем двумя способами количество троек (судья, судья, участник) так, что оба судьей поставили одинаковые оценки участнику. Пусть это число $T$.

С одной стороны, есть $\binom{b}{2}$ способов выбрать пару судьей и по условию есть не более $k$ участников получивших у них одинаковые оценки. Поэтому $T\leq k\binom{b}{2}$.

С другой стороны, рассмотрим произвольного участника. Пусть $s_i$ судьей поставили оценку «удовлетворительно» и $r_i$ судьей поставили оценку «неудовлетворительно». Тогда число пар судьей которые поставили ему одинаковую оценку равно:

$$\binom{s_i}{2}+\binom{r_i}{2}=\frac{s_i^2+r_i^2-s_i-r_i}{2}\geq \frac{(s_i+r_i)^2}{4}-\frac{s_i-r_i}{2}=\frac{n^2}{4}-\frac{n}{2}=\frac{(n-1)^2-1}{4}$$

т.к. $b$ нечетное, $\binom{s_i}{2}+\binom{r_i}{2}\geq \frac{(n-1)^2}{4}$. Поэтому $T\geq \frac{a(b-1)^2}{4}$. Выходит:

$$k\binom{b}{2}\geq T \geq \frac{a(b-1)^2}{4}$$

упрощаем выражение и получаем желаемый результат.