Задача 66558
|
|
 |
Условие
Три богатыря сражаются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще две, а Алёша Попович — четверть всех голов и еще три. Богатыри бьют по одному, в том порядке, в котором считают нужным. Если ни один богатырь не может ударить из-за того, что число голов получится нецелым, то Змей съедает богатырей. Смогут ли богатыри отрубить все головы $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$, то с таким Змеем богатыри справятся.
