Дано: 20 команд, 8 туров, в каждом туре каждая команда играет с 8 другими командами.
Найти: доказать, что найдутся три команды, не сыгравшие между собой ни одного матча.
Решение:
Предположим противное, что нет трех команд, не сыгравших между собой. Тогда для любой тройки команд найдется хотя бы один матч между ними.
Так как в каждом туре каждая команда играет с 8 другими командами, то общее количество матчей за 8 туров составит 20 * 8 / 2 = 80. Это означает, что максимально возможное количество матчей между всеми 20 командами равно 80.
Если все команды сыграли друг с другом по одному разу, общее количество матчей будет равно C(20, 2) = 190, что больше максимально возможного количества матчей.
Таким образом, найдутся три команды, не сыгравшие между собой ни одного матча.
Ответ:
Таким образом, мы доказали, что найдутся три команды, не сыгравшие между собой пока ни одного матча.