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

На танцах было $2 n$ мальчиков и $2 n$ девочек. Боря танцевал со всеми девочками, Аня танцевала со всеми мальчиками, и для любых двух девочек есть ровно n мальчиков, танцевавших ровно с одной из них. Докажите, что каждый мальчик, кроме Бори, танцевал ровно с $n$ девочками.

Подсказка

Рассмотрите вместе с Аней ещё одну (любую) девочку. Что следует их условия?

Решение

Возьмём Аню и любую другую девочку Д. По условию, ровно с одной девочкой из этих двух танцевало ровно $n$ мальчиков. Так как с Аней танцевали все мальчики, то эти $n$ мальчиков танцевали именно с ней, а остальные $n$ мальчиков танцевали и с ней, и с Д. Итак, с каждой девочкой, кроме Ани, танцевали ровно $n$ мальчиков. Возьмём любых двух таких девочек. Пусть с обеими танцевали $m$ мальчиков. Тогда ровно с одной танцевали $n=2(n-m)$ мальчиков, откуда $m=n / 2$ .

Забудем про Аню и Борю. Тогда каждая из девочек танцевала с $n-1$ мальчиком, а с каждыми двумя девочками танцевали $n / 2-1$ мальчиков. Занумеруем мальчиков и пусть $i$ -ый мальчик танцевал с $d_{i}$ девочками. Тогда троек, состоящих из мальчика и двух девочек, с которыми он танцевал, будет $d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2$ . С другой стороны, число таких троек равно $n / 2-1$ , умноженному на количество пар девочек, то есть $(n / 2-1)(2 n-1)(n-1)$ .
Заметим, что

$d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2=\left(d_{1}^{2}+\ldots+d_{2 n-1}^{2}\right) / 2-\left(d_{1}+\ldots+d_{2 n-1}\right) / 2 \text {. }$

Так как $d_{1}+\ldots+d_{2 k-1}=(n-1)(2 n-1)$ (считаем ту же сумму «со стороны девочек»), то получаем, что

$d_{1}^{2}+\ldots+d_{2 n-1}^{2}=2(n / 2-1)(2 n-1)(n-1)+(n-1)(2 n-1)=(n-1)^{2}(2 n-1) .$

С другой стороны, по неравенству между средним арифметическим и средним квадратическим

$d_{1}^{2}+\ldots+d_{2 n-1}^{2} \geq\left(d_{1}+\ldots+d_{2 n-1}\right)^{2} /(2 n-1)=(n-1)^{2}(2 n-1)$

причём равенство достигается только при $d_{1}=\ldots=d_{2 k-1}$ . Итак, все $d_{i}$ равны между собой, откуда $d_{i}=n-1$ , что и (вспомним про Аню!) требовалось доказать.