|
|
 |
Условие
В волейбольном турнире участвовали 110 команд, каждая сыграла с каждой из остальных ровно одну игру (в волейболе не бывает ничьих). Оказалось, что в любой группе из 55 команд найдётся одна, которая проиграла не более чем четырём из остальных 54 команд этой группы. Докажите, что во всём турнире найдётся команда, проигравшая не более чем четырём из остальных 109 команд.
Решение
Лемма. Пусть k ≥ 55, и пусть среди любых k команд найдётся одна, которая проиграла не более чем
четырём из остальных k – 1 команд. Тогда и среди любых k + 1 команд найдётся одна, которая проиграла не более чем четырём из остальных k команд.
Доказательство. Предположив противное, рассмотрим набор из k + 1 команд M = {C1, C2, ..., Ck+1}, для которых требуемой команды не найдётся. Для каждого i = 1, 2, ..., k + 1, если выкинуть из M команду Ci, то среди оставшихся найдётся команда Cj, проигравшая не более чем четырём из остальных. Поскольку Cj не является требуемой для всего набора M, она проиграла также команде Ci и, более того, проиграла ровно пяти командам из M. Назовём такую команду Cj подходящей для команды Ci.
Рассмотрим все команды из M, являющиеся подходящими хотя бы для одной другой команды. Каждая из них является подходящей максимум для пяти из k + 1 ≥ 56 команд; значит, число s подходящих команд не менее 12.
Рассмотрим все игры между подходящими командами. Этих игр всего ½ s(s – 1), и в каждой из них одна из команд проиграла. Значит, одна из подходящих команд проиграла не менее чем ½ s(s – 1) : s = ½ (s – 1) ≥ 5,5, то есть хотя бы шести командам. Но это невозможно.
Теперь покажем индукцией по k = 55, 56, ..., 110, что среди любых k команд найдётся одна, которая проиграла не более чем четырём из остальных k – 1 команд. База при k = 55 верна по условию, а шаг индукции доказан в лемме. Значит, это утверждение верно при k = 110, что и требовалось.
