Задача 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