МОШ 2020, 9 класс, задача 3

Средняя
Комбинаторика
Источник:
Московская олимпиада школьников, Заключительный этап, 2020, 9 класс

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

Верно или неверно?

Войдите, чтобы проверять ответы
Ответ

Ответ. Да, смогут.

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

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

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

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

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

Похожие задачи

МОШ 2026, 9 класс, задача 1

Алиса записала положительные числа a, b, c, d, e (не обязательно целые), а Маруся — числа frac1a, frac1b, frac1c, frac1d, frac1e. Оказалось, что сумма чисел Алисы больше суммы чисел Маруси. Могло ли произведение чисел Алисы оказаться меньше произведения чисел Маруси? (Д. Мухин)
Средняя
Комбинаторика

МОШ 2020, 9 класс, задача 2

Из шести палочек попарно различной длины сложены два треугольника (по три палочки в каждом). Всегда ли можно сложить из них один треугольник, стороны которого состоят из одной, двух и трех палочек соответственно?
Средняя
Комбинаторика

МОШ 2025, 9 класс, задача 2

Можно ли на бесконечной клетчатой плоскости расставить бесконечное количество шахматных коней (не более одного коня в клетку) так, чтобы каждый конь бил ровно 6 других? Напомним, что шахматный конь бьёт 8 клеток, как показано на рисунке. Ходы шахматного коня (А. Тертерян)
Средняя
Комбинаторика

МОШ 2021, 9 класс, задача 2

Клетки бумажного квадрата 8 × 8 раскрашены в два цвета. Докажите, что Арсений может вырезать из него по линиям сетки два квадрата 2 × 2, не имеющих общих клеток, раскраски которых совпадают. (Раскраски, отличающиеся поворотом, считаются разными.) (Л. Попов, А. Гусев)
Средняя
Комбинаторика