В классе 20 учеников. Каждый дружит не менее, чем с 10 другими. Докажите, что в этом классе можно выбрать две тройки учеников так, чтобы любой ученик из одной тройки дружил с любым учеником из другой тройки.
Эта задача была предложена на региональной олимпиаде в 1997 году.
Пусть из вершин выходит соответственно d[1], d[2], ..., d[n] рёбер.
Количество троек вершин, соединённых с первой, равно C(d[1],3), со второй - C(d[2],3), ..., с n-й - C(d[n],3). (Здесь C(m,k) - число способов выбрать k предметов из m различных предметов.)
Чтобы не нашлось двух троек из условия задачи, надо, чтобы никакая пара не встретилась три раза, т.е. необходимо, чтобы
С(d[1],3)+C(d[2],3)+...+C(d[n],3) <= 2 C(20,3).
Но в нашем случае 20*C(10,3) > 2* C(20,3). Значит, есть и искомые тройки.
"Научное" решение мы могли бы получить, используя теорему Кёвари, Шоша, Турана (1955 год). Она говорит о том, что в графе без подграфа K_(m,n) на v вершинах рёбер не очень много. А точнее,
E< 1/2 ((m-1)^1/n v^(2-1/n)+nv).
В нашем случае m=n=3, v=20, а количество рёбер в графе не меньше 20*10/2.