Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, I тур регионального этапа

В группе из 79 школьников у каждого не более 39 знакомых, причем у любого мальчика есть знакомая девочка, а у любой девочки — знакомый мальчик. Может ли оказаться, что все девочки из этой группы имеют в ней поровну знакомых мальчиков, а все мальчики — поровну знакомых девочек? Все знакомства — взаимные. ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. Не может.
Решение. Предположим противное. Пусть в группе $x$ мальчиков и каждый знает $y$ девочек. Тогда всего в группе будет $xy$ знакомств. У всех девочек должно быть поровну из всех этих знакомств, значит $xy$ делится на $79-x.$ Можно считать, что $x \le 39$ (иначе поменяем мальчиков и девочек ролями). Так как $x$ взаимно просто с $79-x,$ на $79-x$ должно делиться число $y.$ Но $79-x \ge 40,$ а $y$ по условию не больше 39. Противоречие.