В первенстве по футболу участвует 16 команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Будем рассматривать несыгранные игры. Условие означает, что не найдётся трёх команд, которые вообще не играли друг с другом. Докажем индукцией по k, что для 2k команд наибольшее число несыгранных игр не больше
База индукции: (оценка очевидна).
Шаг индукции: Пусть доказано для k: докажем для Если несыгранных игр нет, то всё доказано. Иначе выделим произвольные команды A и B, не игравшие между собой. Заметим, что несыгранных игр с участием команд A или B не более (не считая игры между A и B), так как для любой команды C сыграна хотя бы одна из игр AC и BC. Теперь рассмотрим все команды, кроме A и B и применим предположение индукции среди них не сыграно не более игр. Отсюда общее количество несыгранных игр не более что и требовалось доказать.
Подставляя получаем, что число несыгранных игр не более 64, а число всех возможных игр откуда число сыгранных игр не менее
Оценка достигается, если разбить команды на две равные группы, в каждой из которых провести все матчи, а между группами не проводить ни одного.
Ответ: 56 игр.