Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, I тур заключительного этапа
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1.
Ответ. 148.
Решение. Оценка. Назовём доменом команды совокупность всех команд, у которых она выиграла. Команду, в домене которой не менее 99 команд, назовём доминатором.
Пусть в турнире участвовали n команд. Возьмём любые 100 из них. По условию среди них есть доминатор. Заменим его одной из оставшихся команд. В получившейся сотне снова есть доминатор. Повторяя описанную процедуру, пока не побывавшие в сотне команды не закончатся, убеждаемся, что доминаторов у нас по крайней мере n−99.
Пусть доминатор A имеет домен P с наименьшим числом команд. Покажем, что тогда у команд из P выиграли все доминаторы. В самом деле, пусть есть доминатор B с доменом Q, куда не входит какая-то команда K из P. Тогда в силу минимальности домена P в домене Q есть команда M, не входящая в P. Если B≠K и A≠M, то в сотне S команд, составленной из A, B, K, M и любых 96 команд из домена P, нет команды, победившей все остальные: такой командой может быть только A или B, но B проиграла K, а A проиграла M. Если B=K, дополним S до сотни ещё одной командой из P. Тогда A проиграла M, а B проиграла A. Случай, когда A=M, аналогичен, а случай, когда одновременно B=K и A=M, невозможен.
Так как в домене P не меньше 99 команд, там есть команда L, проигравшая хотя бы 49 командам из этого домена — иначе суммарное число поражений в матчах команд из P между собой будет меньше суммарного числа побед. Тогда доминаторов не больше 49 — иначе, взяв 50 доминаторов, команду L и 49 победивших её команд из домена P, мы получили бы сотню (так как в домене P в силу доказанного выше нет доминаторов), в которой команда L проиграла всем остальным. Отсюда n−99≤49, то есть n≤148.
Пример. Разделим 148 команд на 49 доминаторов и 99 доминируемых, проигравших всем доминаторам. Доминируемые команды расположим по кругу, и пусть каждая из них выиграет у 49 следующих за ней по часовой стрелке и проиграет остальным. Доминаторов занумеруем от 1 до 49, и пусть в каждом матче между ними побеждает команда с большим номером. Тогда в любой сотне команд будет хотя бы один доминатор, и доминатор с наибольшим номером победит все остальные команды. С другой стороны, в этой сотне будет хотя бы 51 доминируемая команда, и потому каждая из них победит по крайней мере одну из оставшихся, а каждый доминатор победит их все. Таким образом, команды, проигравшей всем остальным, в сотне не будет.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.