В чемпионате по футболу участвовало 72 команды. Каждые две команды встречались не более одного раза. Оказалось, что любые 48 команд провели между собой не менее 24 игр. Какое наименьшее количество игр могло состояться в этом чемпионате?
Подсказка
Рассмотрите вершину наибольшей степени. Удалите её из графа. Что можно сделать дальше?
Решение
Ответ: 72.
Решение: Обозначим команды точками, а матчи — соединяющими точки отрезками. Возьмем точку, из которой выходит больше всего отрезков, присвоим ей номер 1 и сотрем все исходящие из нее отрезки. После этого рассмотрим точку, из которой выходит больше всего оставшихся отрезков, присвоим ей номер 2, сотрем все исходящие из нее отрезки и т.д. Если из каждой из первых 24 точек перед стиранием выходило не меньше, чем по 2 отрезка, то всего отрезков не менее 
, поскольку команды с номерами от 25 до 72 сыграли между собой не менее 24 матчей. Если же из точки 24 перед стиранием выходило не более 1 отрезка, то из точек от 25 до 72 в этот момент тоже выходит не более, чем по одному отрезку, и среди команд с номерами от 24 до 72 нетрудно найти 48 команд, сыгравшие менее 24 матчей. Итак, матчей сыграно не менее 72 . Пример на 72 матча: команды выстраиваются по кругу, и каждая играет со следующей по часовой стрелке. В самом деле, уберем 24 из этих 72 команд. Они уменьшили число сыгранных матчей максимум на 
, поэтому оставшиеся 48 команд сыграли между собой не меньше 24 матчей.