По верхнему ряду рисунков кроссворд разгадывается следующим образом: «парк, окно, сок», по нижнему ряду — «пар, кок, носок».

Как видим, сообщение «паркокносок» можно прочесть двумя способами. В данном случае информацию, состоящую из одиннадцати букв, вы легко дешифровали, используя подсказки-картинки. Но у криптоаналитика подсказок, как правило, нет.

Рассмотрим аналогичную задачу, связанную с передачей информации, также состоящей из одиннадцати символов, но не сопровождающейся дополнительными подсказками.

Вот ее условие. Некоторый алфавит состоит из шести букв, которые для передачи по телеграфу кодируются одним или двумя знаками следующим образом:

•, —, • •, — —, • —, — •.

При передаче некоего слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка точек и тире, состоящая из одиннадцати знаков.

Сколькими способами можно прочесть переданное слово?

Сделаем задачу более наглядной. Предположим, что вам передали следующее слово:

• • — — • — — — • — •

Попробуйте для начала разобраться с этим частным случаем.

Задача полностью аналогична той, которую вы разгадывали в линейном кроссворде. Но там вы отделяли друг от друга слова, а здесь придется отделить закодированные буквы в слове. Известно, что при передаче телеграмм или радиограмм применяется азбука Морзе, в которой, например, буква А всегда кодируется двумя знаками • —, тогда как буква Е — это одна точка •, а буква Т — просто тире —. Таким образом, получив сообщение из двух знаков • — (в котором преднамеренно пропущен пробел), вы можете его декодировать либо как букву А, либо как две буквы ЕТ.

Теперь попробуйте применить подобный подход для слова из одиннадцати знаков. Не забудьте, что наш этюд называется «Числа Фибоначчи»!

Попробуйте сделать это самостоятельно, потратьте на задачу час, два, три... Столько, сколько вам понадобится. Но не забегайте вперед, чтобы просто прочитать ответ. Задача не так сложна: при ее решении вам не придется воспользоваться ни одной математической формулой!

Подсказка: ответ задачи — двенадцатое число Фибоначчи.

Решим эту задачу подробно — шаг за шагом. Итак, слово длиной в одиннадцать знаков уже задано. Предположим, что сначала нам дана последовательность из 1 знака, затем из 2, 3, ..., 11 знаков. Каждый знак, как вы помните, — это либо точка, либо тире.

Первый шаг. Вначале имеем слово длиной в один знак: *, где * обозначает либо точку, либо тире.

Очевидно, слово у нас прочитается единственным образом. Когда конкретное сообщение из одного знака у вас перед глазами, то вы увидите либо • либо —.

Второй шаг. Теперь задано слово длиной уже в два знака: **.

(*)(*), (**) — два способа декодирования. Других комбинаций попросту нет. Здесь круглыми скобками выделены отдельные буквы (однозначные либо двузначные) в полученном нами слове.

Третий шаг. Имеем слово длиной в три знака: ***.

(*)(*)(*), (*)(**), (**)(*) — уже три способа декодирования (будем располагать последовательность из букв в лексико-графическом порядке их длины — вначале будем стараться выписывать слова, которые начинаются с букв, имеющих наименьшую длину, то есть состоящих из одного знака (*); а слова, содержащие буквы из двойных знаков (**), будем стараться выписывать после первых. Иначе говоря, слово (*)(*)(**) будем писать перед словом (*)(**)(*), так как одиночных знаков слева у первого слова больше, чем у второго). Как мы помним, буквы из трех знаков (***) по условию нашей задачи не существует.

Четвертый шаг. Имеем слово длиной в четыре знака: ****.

(*)(*)(*)(*), (*)(*)(**), (*)(**)(*), (**)(*)(*), (**)(**) — вот так сюрприз! У нас теперь не четыре, как можно было бы ожидать, а целых пять способов декодирования.

Пятый шаг. Имеем слово длиной в пять знаков: *****.

(*)(*)(*)(*)(*), (*)(*)(*)(**), (*)(*)(**)(*), (*)(**)(*)(*), (**)(*)(*)(*), (*)(**)(**), (**)(*)(**), (**)(**)(*) — восемь вариантов декодирования.

Можно продолжать в том же духе. Но попытаемся угадать закономерность, возникающую в ходе решения задачи.

Выпишем количество способов декодирования, полученных на каждом нашем шаге.

Первый шаг — 1 способ.

Второй шаг — 2 способа.

Третий шаг — 3 способа.

Четвертый шаг — 5 способов.

Пятый шаг — 8 способов.

И т. д...

Теперь хорошо видно, что справа у нас стоят числа Фибоначчи: f2 = 1, f3= 2, f4 = 3, f5 = 5, f6 = 8, ... Так как при решении задачи на первом шаге мы получили второе число Фибоначчи f2 = 1, на втором шаге — третье число f3 = 2, то, следовательно, правильным ответом будет двенадцатое число Фибоначчи f12 = 144, так как полученное слово состоит из одиннадцати знаков.

Какая элегантная и красивая задача! И вполне по силам любому. Надеюсь, вы получили море удовольствия при ее самостоятельном решении и не подглядывали в ответ.