Квадраты и домино

Начнем с укладки квадратов и домино. Вообразим длинную горизонтальную рамку размерами 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;

– каждое следующее число получаем сложением двух предыдущих.

Будем обозначать n-ный элемент последовательности Fn, начиная с нуля:

Очередной элемент мы вычисляем по формуле:

Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи[96].

Сумма чисел Фибоначчи

Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F0 + F1 + … + Fn для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.

Обратите внимание на результаты сложения внизу. Видите ли вы закономерность? Повремените немного, прежде чем двигаться дальше: будет лучше, если вы найдете ответ самостоятельно, а не прочтете уже готовое решение.