Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, I тур заключительного этапа

Несколько команд сыграли турнир в один круг, причём ничьих не было. Оказалось, что среди любых 100 команд есть команда, выигравшая у всех остальных 99 команд, но нет команды, проигравшей всем остальным 99 командам. Какое наибольшее число команд могло участвовать в турнире? ( К. Тыщук, Н. Власова, В. Мигрин )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 148.
Решение. Оценка. Назовём доменом команды совокупность всех команд, у которых она выиграла. Команду, в домене которой не менее 99 команд, назовём доминатором.
   Пусть в турнире участвовали $n$ команд. Возьмём любые 100 из них. По условию среди них есть доминатор. Заменим его одной из оставшихся команд. В получившейся сотне снова есть доминатор. Повторяя описанную процедуру, пока не побывавшие в сотне команды не закончатся, убеждаемся, что доминаторов у нас по крайней мере $n-99.$
   Пусть доминатор $A$ имеет домен $P$ с наименьшим числом команд. Покажем, что тогда у команд из $P$ выиграли все доминаторы. В самом деле, пусть есть доминатор $B$ с доменом $Q$, куда не входит какая-то команда $K$ из $P.$ Тогда в силу минимальности домена $P$ в домене $Q$ есть команда $M,$ не входящая в $P.$ Если $B \ne K$ и $A \ne 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 \le 49,$ то есть $n \le 148.$
   Пример. Разделим 148 команд на 49 доминаторов и 99 доминируемых, проигравших всем доминаторам. Доминируемые команды расположим по кругу, и пусть каждая из них выиграет у 49 следующих за ней по часовой стрелке и проиграет остальным. Доминаторов занумеруем от 1 до 49, и пусть в каждом матче между ними побеждает команда с большим номером. Тогда в любой сотне команд будет хотя бы один доминатор, и доминатор с наибольшим номером победит все остальные команды. С другой стороны, в этой сотне будет хотя бы 51 доминируемая команда, и потому каждая из них победит по крайней мере одну из оставшихся, а каждый доминатор победит их все. Таким образом, команды, проигравшей всем остальным, в сотне не будет.