Король Артур vs Дракон

[wpoms.]

У короля Артура должна состояться битва с драконом о трёх головах и трёх хвостах. У короля имеется волшебный меч, который за один удар мог сделать одну (и только одну) из следующих вещей: • срубить одну голову; • срубить две головы; • отрубить хвост; • отрубить два хвоста. Фея Моргана открыла королю Артуру секрет дракона: • если срубить одну голову, то вырастает новая; • если срубить две головы, то ничего не происходит; • вместо отрубленного хвоста вырастают два новых; • при отрубании двух хвостов вырастает новая голова; • дракон умирает, если вы отрубите все три головы и три хвоста. Сколько ударов необходимо сделать, чтобы убить дракона?

@темы: Олимпиадные задачи

Comments

[~ghost]

Всем доброго времени)

например, за 9 ударов - можно..))
первые 3 удара - по одному хвосту (чтобы "наделать" новых - получим 6 хвостов и 3 головы), потом еще 3 удара - по 2 хвоста (убираем хвосты, и получаем четное число голов), и потом 3 удара по 2 головы..

а вообще симпатичная задача ( для 2-ого/ 3-его класса.. )

[litera]

5 ударов - это минимум. Но да, согласна с предыдущим оратором, как-то уж слишком просто))

[Гость]

Не проблема найти вариант, проблема доказать мимнимальность

[Alve]

Как пять? Я насчитала 3:
1. Отрубить 2 хвоста. Появится голова, всего голов станет 4.
2. Отрубить 2 головы.
3. Снова отрубить 2 головы.

[All_ex]

Alve, по условию - дракон умирает, если вы отрубите все три головы и три хвоста.

[litera]

Да уж, неупокоенный безголовый дракон с последним хвостом - зрелище душераздирающее)) Кстати, если последним действием отрубать последние два хвоста при отрубленном всем прочем, это ведь уже считается смертью дракона, и новая голова при этом уже не отрастает? А то иначе 7 действий выходит минимально.

[All_ex]

и новая голова при этом уже не отрастает? - Видимо отрастает...Может он как Кощей ... и смерть его в яйце...

[~ghost]

неупокоенный безголовый дракон с последним хвостом

—
я считала, что только действие

срубить две головы

- когда при этом уже

ничего не происходит

может быть последним в алгоритме (т.е. все такие отрубания голов (попарно) можно поставить в конце алгоритма), т.е. голов надо получить четное количество (прежде чем рубить их парами) - должно быть 2 головы, или 4, или 6 (или... - но чем меньше, тем лучше);
при чем рубить головы по одной - вообще "безыдейно", сразу зацикливаемся =) т.е. ДО того, как рубить головы по 2 шт. - до этого "разбираемся" с хвостами.. — при чем так, чтобы получить четное количество голов..
как-то так у меня и получилось 9 шагов..))