Из условия о том, что каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг, можно сделать вывод, что число подруг у каждого мальчика уникальное.
Итак, число подруг у мальчиков уникальное и равно некоторому числу от 1 до N (всего N вариантов). Но в классе есть только N мальчиков. Значит, в классе есть ровно один мальчик с одной подругой, ровно один мальчик с двумя подругами, ровно один мальчик с тремя подругами, и т.д, ровно один мальчик с N подругами.
Тогда пары будем формировать следующим образом:
1. Берем мальчика с одной подругой и ставим его в пару с этой подругой.
2. Далее берем мальчика с двумя подругами. На данный момент только одна девочка занята в парах, поэтому пару для этого мальчика из двух подруг мы найти точно сможем.
3. На следующих шагах мы последовательно выбираем мальчика с K подругами (где K = 3, 4, ...) и обнаруживаем, что к этому моменту в пары распределена только (K-1) девочка. Значит, найдется такая девочка, которую можно будет поставить этому мальчику в пару.
4. На последнем шаге мы возьмем мальчика, у которого есть N подруг (то есть все девочки класса). Но только (N-1) девочка уже занята в парах. Значит одна оставшаяся девочка будет парой для последнего мальчика.
Получили числа 1 и 1, вместо которых запишем их разность: 1-1=0.
С четверками поступим следующим образом: будем заменять разностью сначала первые два числа, затем другие два числа, а затем и образовавшиеся в результате замен числа. На примере последней четверки:
Вместо чисел 2019 и 2018 запишем их разность: 2019-2018=1, также вместо чисел 2017 и 2016 запишем их разность: 2017-2016=1.
Получили числа 1 и 1, вместо которых запишем их разность: 1-1=0.
Таким образом, у нас образовалось некоторое количество нулей. С замен вида 0-0=0 в конечном счете мы можем получить один ноль.
Пусть в классе N мальчиков и N девочек.
Из условия о том, что каких бы двух мальчиков мы ни взяли, у них будет разное количество подруг, можно сделать вывод, что число подруг у каждого мальчика уникальное.
Итак, число подруг у мальчиков уникальное и равно некоторому числу от 1 до N (всего N вариантов). Но в классе есть только N мальчиков. Значит, в классе есть ровно один мальчик с одной подругой, ровно один мальчик с двумя подругами, ровно один мальчик с тремя подругами, и т.д, ровно один мальчик с N подругами.
Тогда пары будем формировать следующим образом:
1. Берем мальчика с одной подругой и ставим его в пару с этой подругой.
2. Далее берем мальчика с двумя подругами. На данный момент только одна девочка занята в парах, поэтому пару для этого мальчика из двух подруг мы найти точно сможем.
3. На следующих шагах мы последовательно выбираем мальчика с K подругами (где K = 3, 4, ...) и обнаруживаем, что к этому моменту в пары распределена только (K-1) девочка. Значит, найдется такая девочка, которую можно будет поставить этому мальчику в пару.
4. На последнем шаге мы возьмем мальчика, у которого есть N подруг (то есть все девочки класса). Но только (N-1) девочка уже занята в парах. Значит одна оставшаяся девочка будет парой для последнего мальчика.
Разобьем эти числа следующим образом:
(1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), ..., (2016, 2017, 2018, 2019).
С первой тройкой поступим так:
Вместо чисел 3 и 2 запишем их разность: 3-2=1.
Получили числа 1 и 1, вместо которых запишем их разность: 1-1=0.
С четверками поступим следующим образом: будем заменять разностью сначала первые два числа, затем другие два числа, а затем и образовавшиеся в результате замен числа. На примере последней четверки:
Вместо чисел 2019 и 2018 запишем их разность: 2019-2018=1, также вместо чисел 2017 и 2016 запишем их разность: 2017-2016=1.
Получили числа 1 и 1, вместо которых запишем их разность: 1-1=0.
Таким образом, у нас образовалось некоторое количество нулей. С замен вида 0-0=0 в конечном счете мы можем получить один ноль.
Доказано, что один ноль может остаться.