Республиканская юниорская олимпиада по математике. Заключительный этап. 2017-2018 учебный год

2018 волейбольных команд сыграли однокруговой турнир (каждая с каждой сыграла по одному разу), причем в каждом матче играли команды, имевшие к началу этого матча поровну очков. Сколько очков набрала команда-победительница? За победу в волейболе дают 1 очко, за поражение 0 очков, ничьих не бывает.

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

из маил ру

Ключевая вещь - такой турнир получилось провести. Из этого следует очень простое, но нетривиальное следствие.

Допустим, что *в какой-то момент* есть команда, которая набрала ровно k очков. Тогда *по окончанию турнира* обязательно будет команда, которая набрала ровно k очков.

Это очень просто доказывается. Если эта команда ещё не сыграла все свои матчи, то у той команды, с которой она будет играть следующий матч, обязательно будет тоже k очков - и после матча у одной из команд k очков останется. Иными словами, ни одно появившееся количество очков не может окончательно исчезнуть. В частности, в конце турнира обязательно будет команда, которая набрала 0 очков - в начале турнира 0 очков есть (у всех), значит, по окончанию турнира это количество сохранится хотя бы у одной команды.

Теперь будем доказывать, что победитель выиграл у всех. Расположим команды по возрастанию набранных очков. Докажем по индукции, что n-я по счёту команда выиграла у всех предыдущих и набрала ровно n-1 очко.

База индукции: 1-я команда проиграла всем и набрала 0 очков. Такая команда наверняка есть - потому что обязательно есть команда, которая набрала 0 очков. База доказана.

Переход индукции: предположим, что всё так и есть для n = k первых команд. То есть каждая из них выиграла у всех предыдущих и проиграла всем последующим. Значит, каждая из этих следующих набрала не менее k очков. Значит, *в какой-то момент* в турнире появилась команда, которая набрала ровно k очков (перепрыгнуть k не получится, очки добавляются по одному). Значит, *в конце турнира* обязательно есть команда, которая набрала ровно k очков. Значит, эта команда будет как раз на k+1-м месте в нашем рейтинге по возрастанию. Набрала команда эти очки, выиграв у команд с меньшими номерами, а всем остальным командам она проиграла. Значит, наше предположение верно и для n = k+1. Переход доказан.

Значит, команда, набравшая больше всех очков, выиграла у всех команд, которые набрали меньше очков.

2017 очков.