Разделы 
Дополнительно
Задача по математике - 3648
2019-06-13 
В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Решение:
Пусть среди любых, трех команд найдутся две, уже сыгравшие между собой. Выберем команду $A$, которая провела наименьшее количество игр - $k$. Каждая из $k$ команд, уже сыгравших с $A$, как и сама команда $A$, провела не менее $k$ игр. Из $(19 - k)$ команд, не сыгравших с $A$, каждая сыграла со всеми остальными $(18 - k)$ из них - иначе нашлась бы тройка команд, среди которых никакие не играли между собой. Таким образом, удвоенное число всех игр - его можно получить, сложив количества игр, сыгранных всеми командами, - не меньше,
$k^2 + k + (19 - k) (18 - k) = 2k^2 - 36k + 18 \cdot 19 = 2(k -9)^2 + 180 \geq 180$.
Пример ситуации, когда сыграно 90 игр и удовлетворяются условия задачи, дают две группы по 10 команд, в каждой из которых все команды друг с другом сыграли, но ни одна не играла с командой другой группы.
Если изобразить команды точками, а не сыгравшие друг с другом команды соединить отрезком, то получится граф, который при соблюдении условия задачи будет графом без треугольников. Можно доказать, что в таком графе с $n$ вершинами максимум $[n^2 /4]$ ребер.
Ответ: 90 игр.
В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Решение:
Пусть среди любых, трех команд найдутся две, уже сыгравшие между собой. Выберем команду $A$, которая провела наименьшее количество игр - $k$. Каждая из $k$ команд, уже сыгравших с $A$, как и сама команда $A$, провела не менее $k$ игр. Из $(19 - k)$ команд, не сыгравших с $A$, каждая сыграла со всеми остальными $(18 - k)$ из них - иначе нашлась бы тройка команд, среди которых никакие не играли между собой. Таким образом, удвоенное число всех игр - его можно получить, сложив количества игр, сыгранных всеми командами, - не меньше,
$k^2 + k + (19 - k) (18 - k) = 2k^2 - 36k + 18 \cdot 19 = 2(k -9)^2 + 180 \geq 180$.
Пример ситуации, когда сыграно 90 игр и удовлетворяются условия задачи, дают две группы по 10 команд, в каждой из которых все команды друг с другом сыграли, но ни одна не играла с командой другой группы.
Если изобразить команды точками, а не сыгравшие друг с другом команды соединить отрезком, то получится граф, который при соблюдении условия задачи будет графом без треугольников. Можно доказать, что в таком графе с $n$ вершинами максимум $[n^2 /4]$ ребер.
Ответ: 90 игр.
