Математика Олимпиада 7 класс

Предположим, что это не так. Тогда рассмотрим для каждого юноши множество девушек, с которыми он танцевал. Если утверждение задачи неверно, то эти множества образуют вложенную цепочку - для любой пары юношей одно множество содержится в другом. Действительно, если бы они не содержались друг в друге, нашлась бы девкшка Д1, танцевавшая только с первым юношей, и девушка Д2, танцовавшая только со вторым. Далее, рассмотрим максимальное такое множество и юношу Ю с этим множеством. Он не танцевал с некоторой девушкой Д, и поскольку множества вложены, то никто не танцевал с Д. Это противоречит условию.

М-мальчики, Д-девочки
Доказательство от противного. Предположим, что М1 танцевал с Д1, а М2 танцевал с Д2. И М1 танцевал с Д2, а М2 танцевал с Д1.
Есть какое-то множество девочек N1, с которыми танцевал мальчик М1; и множество девочек N2, с которыми танцевал мальчик M2.
Гипотетически мальчик М1 танцевал с любой девочкой из множества N2. Множество N1 можно пополнять до тех пор, пока остаются другие не рассмотренные мальчики помимо М1. И если множество N1 ещё не включает всех девочек, то, ввиду предположения о наличии затанцованного мальчика для каждой девочки, такие мальчики остаются. Значит, М1 танцевал со всеми девочками. А это противоречит условию задачи.
Следовательно, наше предположение от противного неверно.