Республиканская олимпиада по математике, 2009 год, 10 класс

В шахматном турнире участвуют $n$ человек ($n > 1$ — натуральное число). За весь турнир каждый игрок играет с каждым другим ровно одну партию. В каждой партии игроку за выигрыш начисляется 1 очко, за ничью — $0,\!5$ очков, а за проигрыш — 0 очков. Если по окончании турнира игрок набирает не менее $75\%$ от максимального возможного количества очков, которые он может набрать, то ему присваивается разряд. Какое наибольшее количество участников турнира могут получить разряд?

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

Разделим всех участников на две группы: пусть $k$ число людей которые получили разряд и $n-k$ людей, которые разряда не получили.

Каждый игрок сыграет $n-1$ игр, поэтому максимальное количество возможных очков которое может набрать один участник $n-1$.

Заметим что в каждой игре, вне зависимости от результата пара получает в сумме одно очко на двоих.

То есть всего очков $\dbinom{n}{2}=\dfrac{n(n-1)}{2}$. В первой группе каждый получил не менее $\dfrac{3}{4} \cdot (n-1)$, то есть в первой группе количество очков не менее $\dfrac{3}{4} \cdot (n-1)k$.

Во второй группе участники сыграли между собой $\dbinom{n-k}{2}$ матчей, то есть во второй группе количество очков не менее $\dfrac{(n-k)(n-k-1)}{2}$.

Так как сумма очков в первой и во второй группе не превышает общего количества очков получаем неравенство:

$$\dfrac{3}{4} \cdot (n-1)k+\dfrac{(n-k)(n-k-1)}{2} \leq \dfrac{n(n-1)}{2}$$

Откуда $$k \leq \dfrac{n+1}{2}$$

Построить пример никакой трудности не представляет.