Здесь действует так называемая лемма о рукопожатиях.
Рассмотрим граф, вершины которого являются учениками. Между двумя учениками проведем ребро, если они знакомы.
Просуммируем степени вершин. Поскольку каждое ребро имеет ровно две вершины, сумма степеней вершин будет равна удвоенному количеству ребер, однако для нас важнее то, что эта сумма четна.
Поскольку сумма вершин, имеющих четную степень четна, то и сумма вершин, имеющих нечетную степень также четна. Поэтому количество вершин с нечетной степенью четно.
Назовем учеников, имеющих четное кол-во знакомых четными, а нечетное — нечетными.
Заметим, что Гоша не получит подзатыльник только от знакомых, имеющих нечетное количество знакомых. Пусть их . Пусть всего учеников, тогда Гоша получит подзатыльников. Уберем Гошу из рассмотрения. Тогда нечетные знакомые станут четными, нечетные незнакомые останутся нечетными, а четные знакомые станут нечетными. Поэтому сумма количества четных знакомых с нечетными незнакомыми, равная , равна четному числу (после применения леммы). Итак, Гоша получит четное количество подзатыльников. Поскольку он получил 99, его ожидает еще какое-то нечетное количество
Оскільки лицар не може кинути туди 0 монет, бо за умовою він кидає від 1 до 10, то кількість монет завжди змінюється. Подивимося, які числа в межах 100 діляться на 25. Це 25, 50, 75, 100. А на 22: 22,44,66,88.
Кількість монет не може ділитися завжди на 22, бо тоді йому б прийшлося кожного разу додавати 22 монети.
З цієї ж причини не може бути кожного разу 25, бо 25 не може він додавати за умовою.
Нехай спочатку було 25 монет. Щоб число ділилося на 22. він має додати 44-25=19 монет, тому ця ситуація не підходить, бо максимальна кількість 10 монет.
Розглянемо випадок, коли спочатку було число 22, тоді воно ділиться на 22, потім кидає 3 монети, і число ділиться на 25. Здавалося б, що він міг і не помилятися, але візьмемо інше число, яке ділиться на 22, наприклад 88, тоді наступного разу число має ділитися на 25, тобто наступне число 100. Знайдемо різницю між 100 і 88, 100-88=12, а 12 більше, ніж максимальна кількість монет, яку міг закинути чоловік.
Здесь действует так называемая лемма о рукопожатиях.
Рассмотрим граф, вершины которого являются учениками. Между двумя учениками проведем ребро, если они знакомы.
Просуммируем степени вершин. Поскольку каждое ребро имеет ровно две вершины, сумма степеней вершин будет равна удвоенному количеству ребер, однако для нас важнее то, что эта сумма четна.
Поскольку сумма вершин, имеющих четную степень четна, то и сумма вершин, имеющих нечетную степень также четна. Поэтому количество вершин с нечетной степенью четно.
Назовем учеников, имеющих четное кол-во знакомых четными, а нечетное — нечетными.
Заметим, что Гоша не получит подзатыльник только от знакомых, имеющих нечетное количество знакомых. Пусть их
. Пусть всего 
учеников, тогда Гоша получит 
подзатыльников. Уберем Гошу из рассмотрения. Тогда нечетные знакомые станут четными, нечетные незнакомые останутся нечетными, а четные знакомые станут нечетными. Поэтому сумма количества четных знакомых с нечетными незнакомыми, равная 
, равна четному числу (после применения леммы). Итак, Гоша получит четное количество подзатыльников. Поскольку он получил 99, его ожидает еще какое-то нечетное количество
Відповідь:
Він помилявся
Покрокове пояснення:
Оскільки лицар не може кинути туди 0 монет, бо за умовою він кидає від 1 до 10, то кількість монет завжди змінюється. Подивимося, які числа в межах 100 діляться на 25. Це 25, 50, 75, 100. А на 22: 22,44,66,88.
Кількість монет не може ділитися завжди на 22, бо тоді йому б прийшлося кожного разу додавати 22 монети.
З цієї ж причини не може бути кожного разу 25, бо 25 не може він додавати за умовою.
Нехай спочатку було 25 монет. Щоб число ділилося на 22. він має додати 44-25=19 монет, тому ця ситуація не підходить, бо максимальна кількість 10 монет.
Розглянемо випадок, коли спочатку було число 22, тоді воно ділиться на 22, потім кидає 3 монети, і число ділиться на 25. Здавалося б, що він міг і не помилятися, але візьмемо інше число, яке ділиться на 22, наприклад 88, тоді наступного разу число має ділитися на 25, тобто наступне число 100. Знайдемо різницю між 100 і 88, 100-88=12, а 12 більше, ніж максимальна кількість монет, яку міг закинути чоловік.