Возвращаемся к методу математической индукции, одному из самых эффективных методов решения задач. В этом случае задача решается в три шага: База индукции, Предположение индукции, Шаг индукции.
Условие:
Каждый из 2019 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 673 человек, члены которой не выясняли отношений между собой указанным выше способом.
Решение:
Назовем депутатов врагами, если один из них бил другого. При помощи метода математической индукции докажем утверждение: если в парламенте M≥3n-2 депутатов, и каждый дал пощечину ровно одному коллеге, то можно составить парламентскую комиссию из n человек, в которой нет врагов. При n=673 это утверждение соответствует утверждению задачи 2019>2017=3*673-2.
1) База индукции. При n=1 утверждение очевидно.
2) Предположение индукции. Пусть верно для некоторого n=k-1.
3) Шаг индукции. Проверим для n=k. Так как число депутатов равно числу пощечин (равно M), по принципу Дирихле найдется депутат, получивший не более одной пощечины. У него не более двух врагов (его враги — тот, кто его бил и тот, кого он бил). Отправим этого депутата в комиссию, а его врагов (которых не больше двух) выведем из парламента. В парламенте осталось M-3≥3(k-1)-2 депутатов. По предположению индукции, из них можно создать комиссию из k-1 депутатов, не бивших друг друга. Вместе с уже выбранным депутатом они составят комиссию из k депутатов. Ясно, что в этой комиссии никто никого не бил.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
Если вам понравилось, то жмите большой палец вверх. Если очень понравилось - подписывайтесь. Оказывается это важно для развития канала =)
