Question

За смену каждый из учеников Майской Школы, имеющий четное число знакомых среди учеников школы, дал каждому своему знакомому по подзатыльнику. А каждый из остальных учеников школы дал по подзатыльнику каждому незнакомому с ним ученику. Известно, что накануне отъезда Гоша получил 99й подзатыльник. Докажите, что после этого он успел получить еще по меньшей мере один подзатыльник.

Answer 1

Здесь действует так называемая лемма о рукопожатиях.

Рассмотрим граф, вершины которого являются учениками. Между двумя учениками проведем ребро, если они знакомы.

Просуммируем степени вершин. Поскольку каждое ребро имеет ровно две вершины, сумма степеней вершин будет равна удвоенному количеству ребер, однако для нас важнее то, что эта сумма четна.

Поскольку сумма вершин, имеющих четную степень четна, то и сумма вершин, имеющих нечетную степень также четна. Поэтому количество вершин с нечетной степенью четно.

Назовем учеников, имеющих четное кол-во знакомых четными, а нечетное — нечетными.

Заметим, что Гоша не получит подзатыльник только от знакомых, имеющих нечетное количество знакомых. Пусть их $x$. Пусть всего $s$ учеников, тогда Гоша получит $s-x$ подзатыльников. Уберем Гошу из рассмотрения. Тогда нечетные знакомые станут четными, нечетные незнакомые останутся нечетными, а четные знакомые станут нечетными. Поэтому сумма количества четных знакомых с нечетными незнакомыми, равная $s-x$, равна четному числу (после применения леммы). Итак, Гоша получит четное количество подзатыльников. Поскольку он получил 99, его ожидает еще какое-то нечетное количество

Answer 2

Предположим, что Гоша получил 99-й подзатыльник от ученика, который имел четное число знакомых. Поскольку 99 нечетное число, то Гоша был знаком с нечетным числом учеников (так как каждый ученик может дать подзатыльник только ученику, с которым он знаком). Но это означает, что Гоша имел нечетное число знакомых, что противоречит условию.

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

Из обоих предположений возникают противоречия, что означает, что Гоша не мог получить 99-й подзатыльник от ученика среди учеников Майской Школы. Таким образом, после того как Гоша получил 99-й подзатыльник, он успел получить еще по меньшей мере один подзатыльник.