За смену каждый из учеников Майской Школы, имеющий четное число знакомых среди учеников...

Question

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

Answer 1

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

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

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

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

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

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