Question

В футбольном турнире 14 команд сыграли между собой 6 туров — каждая ко- манда сыграла с шестью разными командами. Обязательно ли найдутся три коман- ды, не сыгравшие между собой пока ни одного матча?

Answer 1

Представим, что некие команды (часть общего списка) играли только между собой. Группа таких команд может насчитывать не менее семи - ведь если бы их было меньше, они не смогли бы сыграть шесть раз с разными. Итак, допустим одну такую группу мы нашли, остаётся ещё семь команд, которые как раз составят другую аналогичную группу. Итого мы имеем две группы по семь, которые играли только внутри группы и не играли вне её. Это значит, что можно найти пару команд, не игравших друг с другом (по одной команде из каждой группы), но невозможно будет найти такую тройку (ведь в этой тройке две команды обязательно будут членами одной группы, а значит уже играли между собой)

Answer 2

Ответ:

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

Представим каждую команду в виде вершины графа, а каждый матч между командами в виде ребра. В данном случае у нас есть 14 команд и 6 туров, поэтому у нас будет граф с 14 вершинами и 6 ребрами.

По условию каждая команда сыграла с шестью разными командами. Это означает, что каждая вершина в графе будет иметь степень 6.

Теперь давайте рассмотрим ситуацию, когда все команды сыграли между собой. В этом случае у каждой вершины будет 6 смежных вершин, и общее количество ребер будет равно 14 * 6 /