ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35126
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Четность и нечетность ]
[ Шахматные доски и шахматные фигуры ]
Сложность: 3
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Бился Иван-Царевич со Змеем Горынычем, трёхглавым и трёххвостым. Одним ударом он мог срубить либо одну голову, либо один хвост, либо две головы, либо два хвоста. Но, если срубить один хвост, то вырастут два; если срубить два хвоста – вырастет голова; если срубить голову, то вырастает новая голова, а если срубить две головы, то не вырастет ничего. Как должен действовать Иван-Царевич, чтобы срубить Змею все головы и все хвосты как можно быстрее?


Подсказка

Нужно добиться того, чтобы у Змея Горыныча было чётное число голов и не осталось хвостов. Для достижения этого сначала необходимо добиться определённого числа хвостов.


Решение 1

  Заметим, что рубить одну голову бессмысленно. Остаются три типа ударов: при первом число хвостов увеличивается на 1; при втором число хвостов уменьшается на 2, но число голов увеличивается на 1; при третьем число голов уменьшается на 2.
  Каждый удар удар 2-го типа (и только он) меняет чётность числа голов. Поскольку в начале число голов нечётно, а в конце их должно стать чётное число (0), то количество ударов 2-го типа нечётно. Но одного такого удара недостаточно – им не удастся срубить все хвосты, а удары других типов число хвостов только увеличивают. Поэтому ударов 2-го типа должно быть не меньше трёх.
  При этом вырастет не меньше трёх дополнительных голов, и, чтобы срубить все головы, потребуется не менее трёх ударов 3-го типа.
  Кроме того, три удара 2-го типа срубают шесть хвостов, то есть надо отрастить как минимум три дополнительных хвоста, на что потребуется не менее 3 ударов 1-го типа. Итого, нужно не менее девяти ударов.
  Их и достаточно. Например, сначала Иван может нанести три удара 1-го типа (увеличив число хвостов до шести), затем срубить все хвосты тремя ударами 2-го типа (при этом голов станет шесть), и наконец, срубить эти шесть голов тремя ударами 3-го типа.


Решение 2

  Будем изображать текущее состояние змея (m голов, n хвостов), поставив фигуру на пересечении (m+1)-й строки и (n+1)-го столбца клетчатой доски. Заметим, что после удара Ивана фигура может остаться на месте (что невыгодно) или сдвинуться одним из трёх способов:

  Теперь можно последовательно отмечать на доске клетки, куда фигура может попасть из начальной за определенное число ходов:

  Мы видим, что попасть в левый верхний угол можно лишь на девятом ходу. (Кстати, сделать это можно довольно большим числом способов.)

Источники и прецеденты использования

web-сайт
задача
книга
Автор Козлова Е.Г.
Название Сказки и подсказки
задача
Номер 106

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .