Задача 1. Богатырь и Змей Горыныч

Когда змей не растёт

Пусть сейчас у змея $n$ голов. Взмахом мы отрубаем $1$ или $10$ голов, и остаётся $n-1$ или $n-10$. Если осталось чётное число, голов сразу становится вдвое больше.

Чётность остатка легко предсказать:

• из чётного числа отрубаем $1$ голову — остаётся нечётное, удвоения нет;

• из нечётного отрубаем $10$ голов — остаётся снова нечётное ($10$ — чётное число, чётность оно не меняет), удвоения нет;

• в двух других случаях остаётся чётное число, и голов становится вдвое больше.

У змея $444$ головы — чётное число. Отрубим одну: $444-1=443$ — нечётное, удвоения нет. Теперь можно рубить по $10$ голов: $433,\ 423,\ 413,\ \ldots$ — все эти числа нечётные, и змей не растёт.

Ловушка: три и четыре головы

Рубить по $10$ «до конца» не получится. Посмотрите на последние цифры: $443,\ 433,\ 423,\ \ldots,\ 23,\ 13,\ 3$. Пока число нечётное, взмах по $10$ уменьшает только десятки, а последняя цифра всё время $3$. Так мы придём к $3$ головам.

А с тремя головами беда. Отрубить $10$ нельзя, можно только одну: останется $2$ — чётное число, голов станет $4$. Из четырёх голов — снова только одну: станет $3$. Дальше всегда $3$ или $4$ головы, и победить уже нельзя (рисунок ниже).

Поэтому рубку по $10$ остановим раньше — на $13$ головах: $443-43\cdot 10=13$, это $43$ взмаха. Что делать с $13$ головами, подскажет взгляд с конца.

Посмотрим с конца

Последним взмахом богатырь отрубает последнюю голову: из $1$ головы остаётся $0$. Ноль — чётное число, но удвоенный ноль — снова ноль: $0\cdot 2=0$, голов нет.

К одной голове удобно прийти по десяткам: из $11$ — одним взмахом, из $21$ — двумя. Вообще из любого нечётного числа, которое оканчивается на $1$, рубим по $10$ без всяких удвоений, пока не останется одна голова.

Как получить такое число? У нечётного числа взмах по $10$ последнюю цифру не меняет. Значит, нужно отрубить одну голову от чётного числа, которое оканчивается на $2$: например, $12-1=11$. А $12$ получается удвоением: из $7$ голов отрубаем одну, остаётся $6$, и голов становится $12$.

Получилась концовка из четырёх взмахов:

Отрубаем $1$ голову, ещё $1$, потом $10$ и последнюю.

От 13 голов к 7

Осталось от $13$ голов дойти до нечётного числа, которое оканчивается на $7$, — а от него по десяткам до $7$. Последнюю цифру меняют удвоения, ими и воспользуемся:

• $13-1=12$ — чётное, удвоение: $24$;

• $24-10=14$ — чётное, удвоение: $28$;

• $28-1=27$ — нечётное, удвоения нет;

• $27-10=17$ и $17-10=7$ — нечётные, удвоений нет.

Последняя цифра менялась так: $3 \to 4 \to 8 \to 7$. Змей ненадолго вырос с $13$ до $28$ голов, зато теперь у него $7$ голов, а концовку мы уже знаем. Весь путь от $13$ голов — на рисунке ниже.

Весь пример и ответ для 7 класса

Собираем пример целиком:

• отрубить $1$ голову: $444 \to 443$;

• $43$ раза отрубить по $10$ голов: $443 \to 433 \to \ldots \to 13$;

• отрубить $1$ голову: остаётся $12$, удвоение — $24$;

• отрубить $10$ голов: остаётся $14$, удвоение — $28$;

• отрубить $1$ голову: $27$;

• два раза по $10$ голов: $17$, потом $7$;

• отрубить $1$ голову: остаётся $6$, удвоение — $12$;

• отрубить $1$ голову: $11$;

• отрубить $10$ голов: $1$;

• отрубить последнюю голову: $0$.

Всего взмахов:

По $10$ голов мы рубим, только когда голов не меньше $10$, а удвоения стоят ровно там, где осталось чётное число.

В 7 классе спрашивают: сможет ли богатырь отрубить все головы? Сможет. Обоснование — этот пример: каждый его взмах разрешён условием, а в конце голов не остаётся. Чтобы ответить «сможет», достаточно предъявить один способ и проверить его.

Второй вариант

Во втором варианте Геракл бьётся с Лернейской Гидрой, у которой $333$ головы; правило то же. В 7 классе вопрос второго варианта: «Сможет ли Геракл лишить Гидру всех голов? Не забудьте обосновать свой ответ».

Число $333$ уже нечётное, поэтому первый взмах «одна голова» не нужен: сразу рубим по $10$ голов. Числа $323,\ 313,\ \ldots,\ 13$ остаются нечётными, удвоений нет. От $333$ до $13$ — $32$ взмаха: $333-32\cdot 10=13$. Ещё один взмах дал бы $3$ головы, а из $3$ и $4$ голов не выбраться (шаг 2).

С $13$ головами действуем так же, как в первом варианте (шаги 3–4): 13 → 24 → 28 → 27 → 17 → 7 → 12 → 11 → 1 → 0. Для этого отрубаем по очереди $1,\ 10,\ 1,\ 10,\ 10,\ 1,\ 1,\ 10,\ 1$ голов; удвоения — после первого, второго и шестого из этих взмахов ($12 \to 24$, $14 \to 28$, $6 \to 12$).

Всего $32+9=41$ взмах, и голов не осталось. Перебор всех способов рубить показывает, что быстрее чем за $41$ взмах не получится, и самый короткий путь — именно этот.

Ответ: например, $32$ раза по $10$ голов, затем $1,\ 10,\ 1,\ 10,\ 10,\ 1,\ 1,\ 10,\ 1$; Геракл сможет лишить Гидру всех голов — обоснование тот же проверенный пример.