В классе поровну мальчиков и девочек. Каждый мальчик дружит хотя бы с одной девочкой. При этом, каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг. Докажите, что всегда удастся разбить класс на дружащие пары «мальчик-девочка».
Ответы
Пусть в классе N мальчиков и N девочек.
Из условия о том, что каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг, можно сделать вывод, что число подруг у каждого мальчика уникальное.
Итак, число подруг у мальчиков уникальное и равно некоторому числу от 1 до N (всего N вариантов). Но в классе есть только N мальчиков. Значит, в классе есть ровно один мальчик с одной подругой, ровно один мальчик с двумя подругами, ровно один мальчик с тремя подругами, и т.д, ровно один мальчик с N подругами.
Тогда пары будем формировать следующим образом:
1. Берем мальчика с одной подругой и ставим его в пару с этой подругой.
2. Далее берем мальчика с двумя подругами. На данный момент только одна девочка занята в парах, поэтому пару для этого мальчика из двух подруг мы найти точно сможем.
3. На следующих шагах мы последовательно выбираем мальчика с K подругами (где K = 3, 4, ...) и обнаруживаем, что к этому моменту в пары распределена только (K-1) девочка. Значит, найдется такая девочка, которую можно будет поставить этому мальчику в пару.
4. На последнем шаге мы возьмем мальчика, у которого есть N подруг (то есть все девочки класса). Но только (N-1) девочка уже занята в парах. Значит одна оставшаяся девочка будет парой для последнего мальчика.