ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66558
Темы:    [ Теория чисел. Делимость (прочее) ]
[ Индукция (прочее) ]
[ Инварианты ]
Сложность: 3
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Три богатыря сражаются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще две, а Алёша Попович — четверть всех голов и еще три. Богатыри бьют по одному, в том порядке, в котором считают нужным. Если ни один богатырь не может ударить из-за того, что число голов получится нецелым, то Змей съедает богатырей. Смогут ли богатыри отрубить все головы $20^{20}$-головому Змею?

Решение

Докажем, что богатыри справятся с любым количеством голов Змея, если оно делится на $2$ или на $3$. Для этого удостоверимся, что они всегда могут уменьшить количество голов так, чтобы оно снова делилось на $2$ или на $3$.

Если количество голов делится на $4$, примем его за $4 x$; тогда после удара Алеши Поповича их станет $3 x - 3$, что будет делиться на $3$.

Если количество голов делится на $3$, примем его за $3 x$; тогда после удара Добрыни Никитича их станет $2 x - 2$, что будет делиться на $2$.

Если же количество голов делится на $2$, но не делится на $4$, примем его за $4 x - 2$; тогда после удара Ильи Муромца их станет $2 x - 2$, что снова будет делиться на $2$.

Действуя таким образом, мы сможем каждым ходом уменьшать количество голов, пока не избавимся от них совсем. Поскольку $20^{20}$ делится на $4$, то с таким Змеем богатыри справятся.

Ответ

Да, смогут.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 83
Год 2020
класс
Класс 9
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .