Question

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

Answer 1

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

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

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

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

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

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

Answer 2

Давайте рассмотрим это задание с логической точки зрения.

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

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

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

Таким образом, Гоша получил как минимум два подзатыльника: один, который он дал 99-му ученику, и еще один, который он дал другому ученику.