Глава 9
Числа Фибоначчи
[95]Квадраты и домино
Начнем с укладки квадратов и домино. Вообразим длинную горизонтальную рамку размерами 1 × 10. Мы хотим полностью заполнить ее квадратами 1 × 1 и костяшками домино 1 × 2, не оставив ни единой щели. Вот картинка:
Вопрос: сколькими способами это можно сделать?
Для удобства обозначим число вариантов F10. Перебирать их все и потом пересчитывать – тяжелый труд, чреватый ошибками. Гораздо лучше упростить задачу.
Не будем с места в карьер искать F10, начнем с F1. Это проще простого! Нам нужно заполнить рамку 1 × 1 квадратами 1 × 1 и костяшками домино 1 × 2. Домино не поместится, остается единственное решение: взять один квадрат. Другими словами, F1 = 1.
Теперь разберемся с F2. Размер рамки 1 × 2. Можно заполнить ее двумя квадратами или одной костяшкой домино. Таким образом, есть два варианта, и F2 = 2.
Дальше: сколькими способами можно заполнить рамку 1 × 3? Первый вариант: три квадрата. Два других варианта: одна костяшка домино (две не влезут) и квадрат слева или справа. Итак, F3 = 3.
Еще один шаг: возьмем рамку 1 × 4. На рисунке показаны все варианты заполнения:
Мы нашли пять возможностей, но где гарантия, что мы ничего не упустили? Есть способ проверить себя.
В левом конце рамки может быть или квадрат, или костяшка домино. В верхнем ряду на рисунке – варианты, когда слева квадрат, в нижнем ряду – когда слева домино.
Допустим, слева квадрат. Оставшуюся часть нужно заполнить квадратами и домино. Другими словами, нужно заполнить рамку 1 × 3. Это дает 3 варианта, так как F3 = 3.
Если слева домино, размер оставшейся части 1 × 2, и заполнить ее можно двумя вариантами, так как F2 = 2.
Таким образом, у нас есть 3 + 2 = 5 вариантов, и мы удостоверились, что F4 = 5.
Теперь ваша очередь. Подумайте пару минут и найдите все варианты заполнения для рамки 1 × 5. Их немного. Решение – в конце главы. Можете отвлечься и подумать.
Вернемся к нашим квадратам. Хочется верить, что вы нашли 8 вариантов, так как есть 5 способов укладки, где слева квадрат, и еще 3 способа, где слева домино. Таким образом, F5 = 8.
Подытожим. Мы обозначили FN количество способов заполнения рамки 1 × n квадратами и костяшками домино. Нам необходимо найти F10. Вот что мы уже знаем:
Двигаемся дальше. Чему равно F6? Можно нарисовать все варианты, но это скучно. Лучше разобьем вопрос на две части. Сколькими способами можно заполнить рамку 1 × 6, если слева (a) квадрат и (b) костяшка домино? Хорошая новость: мы уже знаем ответ!
В первом случае нам остается пять квадратов, а мы знаем, что F5 = 8. Во втором случае нужно заполнить четыре квадрата; нам известно, что F4 = 5. Таким образом, F5 + F4 = 13.
Чему равно F7? Исходя из тех же соображений, F7 = F6 + F5 = 13 + 8 = 21. А как насчет F8? Очевидно, F8 = F7 + F6 = 21 + 13 = 34. И так далее. Мы обнаружили следующую взаимосвязь:
Еще несколько шагов – и мы найдем искомое число F10. Правильный ответ – в конце главы.
Числа Фибоначчи
Числа Фибоначчи – это последовательность:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Она выстраивается по таким правилам:
– первые два числа 1 и 1;
– каждое следующее число получаем сложением двух предыдущих.
Будем обозначать n-ный элемент последовательности Fn, начиная с нуля:
F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, …
Очередной элемент мы вычисляем по формуле:
Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи
[96].
Сумма чисел Фибоначчи
Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F0 + F1 + … + Fn для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.
Обратите внимание на результаты сложения внизу. Видите ли вы закономерность? Повремените немного, прежде чем двигаться дальше: будет лучше, если вы найдете ответ самостоятельно, а не прочтете уже готовое решение.
