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

212

355

Посмотреть ответы 2

Ответы на вопрос:

smellofcherry

Математика

4,5(94 оценок)

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

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

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

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

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

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

Huran

Математика

4,6(94 оценок)

6*5*3=90 площадь комнаты 90-9=81 площадь комнаты без окон 81 : 8=10.1 то есть минимум 10 рулона

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Математика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.