|
|
 |
Условие
Бился Иван-Царевич со Змеем Горынычем, трёхглавым и трёххвостым. Одним ударом он мог срубить либо одну голову, либо один хвост, либо две головы, либо два хвоста. Но, если срубить один хвост, то вырастут два; если срубить два хвоста – вырастет голова; если срубить голову, то вырастает новая голова, а если срубить две головы, то не вырастет ничего. Как должен действовать Иван-Царевич, чтобы срубить Змею все головы и все хвосты как можно быстрее?
Подсказка
Нужно добиться того, чтобы у Змея Горыныча было чётное число голов и не осталось хвостов. Для достижения этого сначала необходимо добиться определённого числа хвостов.
Решение 1
Заметим, что рубить одну голову бессмысленно. Остаются три типа ударов: при первом число хвостов увеличивается на 1; при втором число хвостов уменьшается на 2, но число голов увеличивается на 1; при третьем число голов уменьшается на 2.
Каждый удар удар 2-го типа (и только он) меняет чётность числа голов. Поскольку в начале число голов нечётно, а в конце их должно стать чётное число (0), то количество ударов 2-го типа нечётно. Но одного такого удара недостаточно – им не удастся срубить все хвосты, а удары других типов число хвостов только увеличивают. Поэтому ударов 2-го типа должно быть не меньше трёх.
При этом вырастет не меньше трёх дополнительных голов, и, чтобы срубить все головы, потребуется не менее трёх ударов 3-го типа.
Кроме того, три удара 2-го типа срубают шесть хвостов, то есть надо отрастить как минимум три дополнительных хвоста, на что потребуется не менее 3 ударов 1-го типа. Итого, нужно не менее девяти ударов.
Их и достаточно. Например, сначала Иван может нанести три удара 1-го типа (увеличив число хвостов до шести), затем срубить все хвосты тремя ударами 2-го типа (при этом голов станет шесть), и наконец, срубить эти шесть голов тремя ударами 3-го типа.
Решение 2
Будем изображать текущее состояние змея (m голов, n хвостов), поставив фигуру на пересечении (m+1)-й строки и (n+1)-го столбца клетчатой доски. Заметим, что после удара Ивана фигура может остаться на месте (что невыгодно) или сдвинуться одним из трёх способов:
Мы видим, что попасть в левый верхний угол можно лишь на девятом ходу. (Кстати, сделать это можно довольно большим числом способов.)
