МОШ 2023, 11 класс, задача 4
В турнире по теннису (где не бывает ничьих) участвовало более спортсменов. Каждый игровой день каждый теннисист принимал участие ровно в одной игре.
К завершению турнира каждый сыграл с каждым в точности один раз. Назовём игрока упорным, если он выиграл хотя бы один матч и после первой своей победы ни разу
не проигрывал. Остальных игроков назовём неупорными. Верно ли, что игровых дней,
когда была встреча между неупорными игроками, больше половины?
(Б. Р. Френкин)
Решение. В последний день все упорные выиграли. Значит, их не больше половины. Если их меньше половины, то каждый день была встреча между неупорными игроками. Остаётся рассмотреть
случай, когда количество упорных составляет половину от общего количества игроков 2k.
Такой турнир длился 2k-1 дней, и нужно доказать, что были хотя бы дней, когда была встреча
между неупорными. Это равносильно тому, что было хотя бы дней, в которые была встреча между
упорными, так как и тех, и других — ровно половина (если все упорные играют с неупорными, то
в этих встречах участвуют все неупорные, и обратно).
Предположим противное: пусть встречи между неупорными игроками проходили менее, чем в
половине всех дней турнира. Тогда, в силу замечания выше, то же самое можно сказать и про
встречи между упорными игроками. Так как всего упорных игроков , каждый упорный играл
с упорными день. Поэтому единственный возможный вариант, при котором встречи между
упорными игроками проходили менее чем в половине дней турнира, — это когда все упорные играют
между собой в одни и те же дни. Другими словами можно сказать, что упорные проводят в этот
день между собой минитурнир, а такое возможно только если число упорных игроков чётно.
Вспомним теперь, что , то есть , а поскольку — чётное, то . Тогда в первый из
дней минитурнира играли по крайней мере две пары упорных игроков, а значит было хотя бы два
упорных, победивших в этот день. В дальнейшем они должны сыграть между собой, но тогда один
из них проиграет после того как выиграл. Противоречие. Значит, наше предположение неверно, и
игровых дней, когда была встреча между неупорными игроками, не менее половины.