Вы – расхититель гробниц. Нужно пройти над пропастью по лестнице, охраняемой Сфинксом. Как водится, Сфинкс задает загадку. Решите задачу неверно – и лестница провалится в пропасть, когда вы по ней пойдете.
Условие задачи. Строительными блоками лестницы являются балки с квадратным сечением, соединенные по три таким образом, что срез имеет форму тримино (как у правой фигуры на рисунке). Для каких n можно составить лестницу из таких тройных блоков, если n – число квадратных балок в ее основании? На рисунке приведено поперечное сечение лестницы для n = 8 .
Другими словами, какие лестничнообразные фигуры с основанием из n квадратов можно разрезать нацело на тримино?
Эта задача – пятнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – алгоритмическую задачу о прыгающих лягушках. Ответ и новая задача будут опубликованы в 14:00 в субботу.
Решение алгоритмической задачи о лягушках
Если вы не решали эту задачу, прежде чем читать приведенный ниже текст, прочитайте условие и попробуйте решить самостоятельно!
Решение. Движение лягушки сводится либо к прыжку через лягушку противоположного вида, либо к переходу лягушки на соседнюю пустую клетку. Таким образом, если мы найдем общее количество прыжков и переходов, мы узнаем общее количество ходов.
Прыжок – единственный способ, которым лягушки противоположного вида могут преодолеть друг друга. Мы сталкивались с этим ранее в предыдущих задачах: получается, что для того, чтобы преодолеть друг друга, им необходимо совершить n 2 прыжков в случае n настоящих и n виртуальных лягушек.
Сдвиг. Рассмотрим далее ситуацию для лягушек одного вида. Мы знаем, что они не могут перепрыгивать друг через друга. Первая лягушка переместится на n + 1 клеток и окажется в ячейке n + 2 , вторая лягушка передвинется на n + 1 клеток до ячейки n + 3 , и т. д. Чтобы оказаться в нужной позиции, вместе все лягушки одного вида должны переместиться на n (n + 1) клеток. Аналогично должны сделать их виртуальные аналоги. То есть все эти реальные и виртуальные земноводные переместятся на 2 n (n + 1) клеток. Поскольку один прыжок охватывает две ячейки, и их n 2 , количество сдвигов должно составить 2n (n + 1) – 2n 2 = 2n .
Алгоритм. Существует два симметричных алгоритма для решения головоломки: один начинается со сдвига крайней к пустой ячейки настоящей лягушки, другой – со сдвига виртуальной. Опишем первый. Алгоритм может быть получен методом грубой силы: его ходы определены однозначно, потому что альтернативные ходы приводят к очевидным тупиковым ситуациям. В частности, когда есть выбор между сдвигом и прыжком, должен быть сделан прыжок.
Ниже приведены алгоритмы для n = 2 и n = 3 соответственно. Настоящие лягушки обозначены T , виртуальные – F .
Решение для n = 2 Решение для n = 3
Головоломка может быть легко обобщена на случай с m и n лягушками разных видов. Общее количество необходимых ходов равно mn + m + n , из которых mn – количество прыжков, а m + n – число сдвигов.
Ответ: для 3 лягушек с каждой стороны достаточно 15 ходов.
Ответ на вопрос со звёздочккой: Для m и n лягушек достаточно mn + m + n ходов.
Как ответили читатели Библиотеки программиста? Сам ответ о числе переходов первым дал пользователь wil4, но без указания решения:
Первым ответ с решением, но с чуть большим числом ходов дал пользователь mr.fantazylight:
В комментариях к решению задачи мы обсудили, откуда берутся два лишних хода.
Программное решение, находящее алгоритм для любого m и n , реализовал на С++ пользователь krotbsod. Вот пример для m = 3 и n = 5 :