Олимпиадная задача по комбинаторике: есть ли тройка команд без матчей?
Задача
В футбольном чемпионате участвуют 18 команд. На сегодняшний день проведено 8 туров (в каждом туре все команды разбиваются на пары и в каждой паре команды играют друг с другом, причём пары не повторяются). Верно ли, что найдутся три команды, которые не сыграли ни одного матча между собой?
Решение
Рассмотрим одну из команд, обозначив её через А. За 8 туров она сыграла с восемью командами, а с девятью – не сыграла. Если среди этих девяти есть две команды В и С, не сыгравшие между собой, то А, В и С образуют искомую тройку.
В противном случае эти 9 команд сыграли между собой полный круговой турнир. Для этого потребовалось 9·8 : 2 = 36 матчей. Однако в каждом туре они смогли сыграть между собой не более четырёх матчей, поэтому за 8 туров таких матчей могло быть не более 32. Противоречие.
Ответ
Верно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь