13 марта 2017
В закладки
Обсудить
Задача 30
В первенстве по футболу участвует 20 команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трёх команд нашлись две, уже сыгравшие между собой?
Решение
Пусть среди любых трёх команд найдутся две команды, уже игравшие между собой. Выберем команду A, которая провела наименьшее количество игр – k. Следовательно, каждая из k команд, уже сыгравших с командой A, провела не менее k игр. Тогда, каждая из (19-k) команд, не сыгравших с A, сыграла со всеми (18-k) командами. В противном случае, нашлась бы тройка команд, не игравших между собой. Удвоенное число всех игр, сыгранных всеми командами, не меньше чем:
\({k^2} + k + \left( {19 - k} \right)\left( {18 - k} \right) = 2{k^2} - 36k + 18 \cdot 19 = 2{\left( {k - 9} \right)^2} + 180.\)
Таким образом, наименьшее число игр N определяется из равенства:
\(N \ge {\left( {k - 9} \right)^2} + 90 \ge 90\).
Такое значение достигается, например при двух группах по 10 команд, в каждой из которых все команды друг с другом сыграли, но ни одна не играла с командой другой группы.
Ответ: 90.
Решение
Пусть среди любых трёх команд найдутся две команды, уже игравшие между собой. Выберем команду A, которая провела наименьшее количество игр – k. Следовательно, каждая из k команд, уже сыгравших с командой A, провела не менее k игр. Тогда, каждая из (19-k) команд, не сыгравших с A, сыграла со всеми (18-k) командами. В противном случае, нашлась бы тройка команд, не игравших между собой. Удвоенное число всех игр, сыгранных всеми командами, не меньше чем:
\({k^2} + k + \left( {19 - k} \right)\left( {18 - k} \right) = 2{k^2} - 36k + 18 \cdot 19 = 2{\left( {k - 9} \right)^2} + 180.\)
Таким образом, наименьшее число игр N определяется из равенства:
\(N \ge {\left( {k - 9} \right)^2} + 90 \ge 90\).
Такое значение достигается, например при двух группах по 10 команд, в каждой из которых все команды друг с другом сыграли, но ни одна не играла с командой другой группы.
Ответ: 90.