Головоломка Каноника
Этот персонаж присоединился к компании по дороге и
приветствовал ее словами: "Да охраняет Вас крест Христов; я вас хотел догнать, Чтоб в
Кентербери путь свой продолжать В приятном обществе совместно с вами". Разумеется,
его пригласили присоединиться к компании, с тем, однако, чтобы он придумал
головоломку. Каноник показал им ромбовидное расположение букв, представленное на
рисунке, и сказал:
- Я называю это головоломкой крысолова. Сколькими различными способами можете вы
прочитать фразу "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.
,
|