Question

Комбинаторика: В розыгрыше первенства мира по футболу участвуют 20 команд. Какое наименьшее количество игр должно быть сыграно, чтобы среди любых трех команд нашлись две, которые уже сыграли между собой ?

Answer 1

Для решения данной задачи, нам нужно найти наименьшее количество игр, при котором среди любых трех команд будут две, уже сыгравшие друг с другом.

Давайте рассмотрим все возможные комбинации из трех команд и посмотрим, какие игры они могут сыграть.
Изначально у нас есть 20 команд, то есть 20 возможных комбинаций из трех команд.

Комбинация 1: Команда 1, команда 2, команда 3
Комбинация 2: Команда 1, команда 2, команда 4
Комбинация 3: Команда 1, команда 2, команда 5
...
Комбинация 19: Команда 1, команда 2, команда 20
Комбинация 20: Команда 1, команда 3, команда 4
...
Комбинация 399: Команда 19, команда 20, команда 1
Комбинация 400: Команда 20, команда 1, команда 2

Теперь нам нужно понять, сколько игр должно быть сыграно, чтобы найти хотя бы одну совпадающую комбинацию. Предположим, что каждая команда сыграла только с каждой другой командой один раз.

Команда 1 сыграла с каждой из оставшихся 19 команд. (19 игр)
Команда 2 сыграла с каждой из оставшихся 18 команд. (18 игр)
Команда 3 сыграла с каждой из оставшихся 17 команд. (17 игр)
...
Команда 19 сыграла с каждой из оставшихся 1 командой. (1 игра)
Команда 20 уже сыграла со всеми остальными командами.

Общее число игр равно сумме всех чисел от 1 до 19 (так как 20 команда уже сыграла со всеми) и равно:
19 + 18 + 17 + 16 + ... + 2 + 1 = 190 игр.

То есть, нам понадобится сыграть минимум 190 игр, чтобы в среди любых трех команд были две, которые уже сыграли между собой.

В приведенном ответе мы подошли к решению на основе сочетаний и учли все возможности, учитывая условие задачи. Наш ответ является конкретным числом, которое представляет наименьшее количество игр для достижения заданного условия.