МОШ 2020, 9 класс, задача 3
Три богатыря сражаются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще две, а Алёша Попович — четверть всех голов и еще три. Богатыри бьют по одному, в том порядке, в котором считают нужным. Если ни один богатырь не может ударить из-за того, что число голов получится нецелым, то Змей съедает богатырей. Смогут ли богатыри отрубить все головы -головому Змею?
Ответ. Да, смогут.
Решение. Докажем, что богатыри справятся с любым количеством голов Змея, если оно делится на или на . Для этого удостоверимся, что они всегда могут уменьшить количество голов так, чтобы оно снова делилось на или на .
Если количество голов делится на , примем его за ; тогда после удара Алёши Поповича их станет , что будет делиться на .
Если количество голов делится на , примем его за ; тогда после удара Добрыни Никитича их станет , что будет делиться на .
Если же количество голов делится на , но не делится на , примем его за ; тогда после удара Ильи Муромца их станет , что снова будет делиться на .
Действуя таким образом, мы сможем каждым ходом уменьшать количество голов, пока не избавимся от них совсем. Поскольку делится на , то с таким Змеем богатыри справятся.