Дано: В розыгрыше первенства по футболу участвуют 20 команд.
Найти: Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Решение:
Для того чтобы найти минимальное количество игр, необходимо создать худший сценарий, когда каждые две команды ещё не играли друг с другом. Таким образом, если выберем одну команду, она должна сыграть со всеми остальными командами.
Количество игр, необходимое для каждой команды сыграть со всеми остальными, можно найти суммируя числа от 1 до (20-1), то есть 1 + 2 + 3 + ... + 19 = 190. Однако, так как каждая игра учитывается дважды (для каждой из двух команд), общее количество игр нужно разделить пополам: 190 / 2 = 95.
Ответ: Чтобы среди любых трех команд найти две, уже сыгравшие между собой, необходимо провести как минимум 95 игр.