Головоломка Каноника

Этот персонаж присоединился к компании по дороге и приветствовал ее словами: "Да охраняет Вас крест Христов; я вас хотел догнать, Чтоб в Кентербери путь свой продолжать В приятном обществе совместно с вами". Разумеется, его пригласили присоединиться к компании, с тем, однако, чтобы он придумал головоломку. Каноник показал им ромбовидное расположение букв, представленное на рисунке, и сказал:


- Я называю это головоломкой крысолова. Сколькими различными способами можете вы прочитать фразу "Was it a rat I saw" (He крысу ли я видел?)
Вы можете двигаться в любом направлении вперед и назад, вверх и вниз, но только любые две последовательные буквы должны находиться рядом друг с другом.

Ответ

Число различных способов равно 63 504. Общая формула для таких расположении, когда число букв в предложении-палиндроме равно 2n + 1, без диагоналей имеет вид [4(2n- 1)]2.
Я думаю, что было бы неплохо привести здесь формулу для общего решения каждой из четырех наиболее обычных форм такой ромбовидной головоломки. Под словом "прямая" я понимаю полную диагональ. Так, в случаях а, б, в и г прямые соответственно содержат 5, 5, 7 и 9 букв. В случае а есть непалиндромная прямая (соответствующее слово BOY - мальчик), и общее решение для таких случаев, где эта прямая состоит из 2n + 1 букв, имеет вид 4(2n - 1). Когда прямая представляет собой единственный палиндром со средней буквой в центре, как в случае б (соответствующее слово LEVEL - уровень), то общая формула имеет вид 4[(2n - 1)]2. Именно к этому типу относится головоломка крысолова. В случаях б и г мы имеем двойные палиндромы, но весьма различных типов. В случае в, где прямая содержит 4n - 1 букву, общее решение имеет вид 4(22n - 2). Но случай г - самый трудный изо всех.
Я хочу подчеркнуть еще раз, что в рассматриваемых ромбах:
1) не разрешается чтение по диагоналям (это особенно важно в случаях, когда такое чтение в принципе возможно);
2) начинать можно с любого места;
3) читать можно, двигаясь вперед и назад и используя при однократном чтении некоторые буквы более одного раза, но одну и ту же букву нельзя использовать дважды подряд.
Последнее условие легче понять, если читатель обратится к случаю в, где нельзя двигаться вперед и назад, не использовав два раза подряд первое O, что запрещает пункт (3). В случае г все устроено совсем иначе, и именно отсюда возникают большие трудности. Формула для случая г имеет вид:


где число букв на прямой равно 4n + 1. В приведенном здесь примере n = 2, а число способов равно 400.