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

Пусть в классе \(n\) мальчиков и \(n\) девочек. Рассмотрим, сколько подруг есть у каждого мальчика.

Каждый мальчик дружит хотя бы с одной девочкой, значит число его подруг не меньше \(1\). Больше \(n\) подруг быть не может, потому что всего девочек \(n\). По условию у любых двух мальчиков количество подруг разное.

Значит, у мальчиков разные числа подруг из набора:

\[1,2,3,\ldots,n\]

Теперь возьмём любых \(k\) мальчиков. Пусть они вместе дружат с \(m\) девочками. Тогда каждый из этих \(k\) мальчиков имеет не больше \(m\) подруг, потому что все его подруги входят в эту группу из \(m\) девочек.

Но у этих \(k\) мальчиков количества подруг разные и положительные. Чтобы среди положительных чисел было \(k\) разных чисел, не превосходящих \(m\), нужно, чтобы \(m\ge k\).

То есть любые \(k\) мальчиков вместе дружат хотя бы с \(k\) девочками. По теореме Холла это означает, что можно каждому мальчику выбрать свою девочку-подругу так, чтобы девочки не повторялись.

Значит, класс всегда можно разбить на дружащие пары «мальчик-девочка».

0 0 Пожаловаться