Задача 025 — Задачи на Графы

2016 мальчиков выбирают девочек. Каждый мальчик выбирает ровно двух девочек: одну блондинку и одну брюнетку. Оказалось, что для любого натурального числа $k, 1 \leq k \leq 80$ , найдется девочка (блондинка или брюнетка), которую выбрали ровно $k$ мальчиков. Докажите, что какие-то два мальчика выбрали одних и тех же девочек.

Подсказка

Зафиксируйте 80 вершин со степенями $1,2, \ldots, 80$ соответственно.

Решение

Рассмотрим двудольный (мульти)граф, где вершины — блондинки и брюнетки, а рёбра — выборы мальчиков. В нем 2016 рёбер. Надо доказать, что есть два ребра с общими концами.

Зафиксируем 80 вершин со степенями $1,2, \ldots, 80$ соответственно; назовём их выбранными. Пусть имеется $k$ рёбер, оба конца которых выбраны; также назовём их выбранными. Тогда рёбер, один конец которых выбран, будет $1+2+\ldots+80-2 k$ . С другой стороны, их не больше, чем 2016- $k$ , откуда $k \geq 1+2+\ldots+80-2016=1224$ .

Рассмотрим выбранные вершины со степенями $1,2, \ldots, 26$ . Из них исходит не более $1+2+\ldots+26=351$ выбранного ребра. Значит, остальные 54 вершины связывают не менее $1224-351=873$ рёбер. С другой стороны, пусть среди этих 54 вершин $x$ блондинок и $54-x$ брюнеток, и между любыми двумя вершинами — не более одного ребра. Тогда всего между этими вершинами не более $x(54-x) \leq(x+54-x)^{2} / 2^{2}=27^{2}=729$ рёбер. Противоречие.