Олимпиада им. Эйлера

Оценка. Назовём доменом команды совокупность всех команд, у которых она выиграла. Команду, в домене которой не менее команд, назовём доминатором.

Пусть в турнире участвовали команд. Возьмём любые из них. По условию среди них есть доминатор. Заменим его одной из оставшихся команд. В получившейся сотне снова есть доминатор. Повторяя описанную процедуру, пока не побывавшие в сотне команды не закончатся, убеждаемся, что доминаторов у нас по крайней мере

Пусть доминатор имеет домен с наименьшим числом команд. Покажем, что тогда у команд из выиграли все доминаторы. В самом деле, пусть есть доминатор с доменом куда не входит какая-то команда из Тогда в силу минимальности домена в домене есть команда не входящая в Если и то в сотне команд, составленной из и любых команд из домена нет команды, победившей все остальные: такой командой может быть только или но проиграла а проиграла Если дополним до сотни ещё одной командой из Тогда проиграла а проиграла Случай, когда аналогичен, а случай, когда одновременно и невозможен.

Так как в домене не меньше команд, там есть команда проигравшая хотя бы командам из этого домена — иначе суммарное число поражений в матчах команд из между собой будет меньше суммарного числа побед. Тогда доминаторов не больше — иначе, взяв доминаторов, команду и победивших её команд из домена мы получили бы сотню (так как в домене в силу доказанного выше нет доминаторов), в которой команда проиграла всем остальным. Отсюда то есть

Пример. Разделим команд на доминаторов и доминируемых, проигравших всем доминаторам. Доминируемые команды расположим по кругу, и пусть каждая из них выиграет у следующих за ней по часовой стрелке и проиграет остальным. Доминаторов занумеруем от до и пусть в каждом матче между ними побеждает команда с большим номером. Тогда в любой сотне команд будет хотя бы один доминатор, и доминатор с наибольшим номером победит все остальные команды. С другой стороны, в этой сотне будет хотя бы доминируемая команда, и потому каждая из них победит по крайней мере одну из оставшихся, а каждый доминатор победит их все. Таким образом, команды, проигравшей всем остальным, в сотне не будет.