В классе поровну мальчиков и девочек. Каждый мальчик дружит хотя бы с одной девочкой. При этом, каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг. Докажите, что всегда удастся разбить класс на дружащие пары «мальчик-девочка».

Пусть в классе N мальчиков и N девочек.

Из условия о том, что каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг, можно сделать вывод, что число подруг у каждого мальчика уникальное.

Итак, число подруг у мальчиков уникальное и равно некоторому числу от 1 до N (всего N вариантов). Но в классе есть только N мальчиков. Значит, в классе есть ровно один мальчик с одной подругой, ровно один мальчик с двумя подругами, ровно один мальчик с тремя подругами, и т.д, ровно один мальчик с N подругами.

Тогда пары будем формировать следующим образом:

1. Берем мальчика с одной подругой и ставим его в пару с этой подругой.

2. Далее берем мальчика с двумя подругами. На данный момент только одна девочка занята в парах, поэтому пару для этого мальчика из двух подруг мы найти точно сможем.

3. На следующих шагах мы последовательно выбираем мальчика с K подругами (где K = 3, 4, ...) и обнаруживаем, что к этому моменту в пары распределена только (K-1) девочка. Значит, найдется такая девочка, которую можно будет поставить этому мальчику в пару.

4. На последнем шаге мы возьмем мальчика, у которого есть N подруг (то есть все девочки класса). Но только (N-1) девочка уже занята в парах. Значит одна оставшаяся девочка будет парой для последнего мальчика.