Математикадан 39-шы халықаралық олимпиада, 1998 жыл, Тайбэй


Жарысқа $a$ қатысушы қатысты, оларды $b$ әділ-қазылар бағалады, мұндағы $b$ — 3-тен кем емес тақ сан. Әрбір қатысушыға әділ-қазылар "қанағаттанарлық" немесе "қанағаттанарлық емес" деп баға қойды. Кез келген екі әділ-қазы үшін, олардан алған бағалары бірдей $k$ қатысушыдан аспайтындай $k$ саны бар. $\dfrac{k}{a}\ge \dfrac{b-1}{2b}$ теңсіздігін дәлелдеңіздер.
посмотреть в олимпиаде

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

пред. Правка 3   11
2023-01-05 16:08:31.0 #

Посчитаем двумя способами количество троек (судья, судья, участник) так, что оба судьей поставили одинаковые оценки участнику. Пусть это число $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}$$

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