Математикадан 39-шы халықаралық олимпиада, 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}$$

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