Республиканская юниорская олимпиада по математике. Заключительный этап. 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 очков.