Эйлер атындағы олимпиада, 2020-2021 оқу жылы, аймақтық кезеңнің 1 туры

79 оқушыдан тұратын топта әр оқушының 39 көп емес танысы бар, сонымен қатар әр ұл балада таныс қыз бар, ал әр қыз балада таныс ұл бар. Осы топта кез келген екі қыздың таныс ұлдар саны өзара тең, ал кез келген екі ұлдың таныс қыздар саны өзара тең болуы мүмкін бе? (Егер бірінші оқушы екінші оқушымен таныс болса, онда екінші оқушы да бірінші оқушымен таныс деп есептеңдер.) ( С. Берлов )

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

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