Республиканская юниорская олимпиада по математике. Заключительный этап. 2017-2018 учебный год
Комментарий/решение:
из маил ру
Ключевая вещь - такой турнир получилось провести. Из этого следует очень простое, но нетривиальное следствие.
Допустим, что *в какой-то момент* есть команда, которая набрала ровно k очков. Тогда *по окончанию турнира* обязательно будет команда, которая набрала ровно k очков.
Это очень просто доказывается. Если эта команда ещё не сыграла все свои матчи, то у той команды, с которой она будет играть следующий матч, обязательно будет тоже k очков - и после матча у одной из команд k очков останется. Иными словами, ни одно появившееся количество очков не может окончательно исчезнуть. В частности, в конце турнира обязательно будет команда, которая набрала 0 очков - в начале турнира 0 очков есть (у всех), значит, по окончанию турнира это количество сохранится хотя бы у одной команды.
Теперь будем доказывать, что победитель выиграл у всех. Расположим команды по возрастанию набранных очков. Докажем по индукции, что n-я по счёту команда выиграла у всех предыдущих и набрала ровно n-1 очко.
База индукции: 1-я команда проиграла всем и набрала 0 очков. Такая команда наверняка есть - потому что обязательно есть команда, которая набрала 0 очков. База доказана.
Переход индукции: предположим, что всё так и есть для n = k первых команд. То есть каждая из них выиграла у всех предыдущих и проиграла всем последующим. Значит, каждая из этих следующих набрала не менее k очков. Значит, *в какой-то момент* в турнире появилась команда, которая набрала ровно k очков (перепрыгнуть k не получится, очки добавляются по одному). Значит, *в конце турнира* обязательно есть команда, которая набрала ровно k очков. Значит, эта команда будет как раз на k+1-м месте в нашем рейтинге по возрастанию. Набрала команда эти очки, выиграв у команд с меньшими номерами, а всем остальным командам она проиграла. Значит, наше предположение верно и для n = k+1. Переход доказан.
Значит, команда, набравшая больше всех очков, выиграла у всех команд, которые набрали меньше очков.
2017 очков.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.