Question

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

Для доказательства данного утверждения воспользуемся принципом Дирихле, который гласит: если n объектов размещены в m ячейках (где n > m), то хотя бы в одной ячейке должно быть размещено по крайней мере два объекта.

Давайте представим, что у нас есть класс, в котором поровну мальчиков и девочек, и каждый мальчик дружит хотя бы с одной девочкой. Мы можем представить каждого мальчика как объект (назовем их M1, M2, M3, и так далее) и каждую девочку как объект (назовем их D1, D2, D3, и так далее).

Теперь давайте предположим, что у нас есть два мальчика Mx и My, и они дружат с одной и той же девочкой Dz. Тогда у нас будет следующая ситуация:

Mx - Dz - My

Таким образом, у нас есть два мальчика, Mx и My, которые дружат с одной и той же девочкой Dz. Это нарушает условие, что у двух мальчиков не может быть одинаковое количество подруг. Следовательно, мы применили принцип Дирихле, и это означает, что всегда существуют хотя бы два мальчика, дружащих с одной и той же девочкой.

Теперь мы можем использовать это утверждение для построения дружащих пар "мальчик-девочка". Начнем с любой пары мальчик-девочка, которые дружат друг с другом, и удалим их из рассмотрения. Затем выберем еще одну пару мальчик-девочка, которые дружат друг с другом, и также удалим их из рассмотрения. Продолжим этот процесс, выбирая пары и удаляя их, пока у нас не останется пара мальчик-девочка, которые дружат друг с другом. Таким образом, мы создадим дружащие пары "мальчик-девочка", и каждый мальчик будет дружить с хотя бы одной девочкой, как требовалось доказать.