Книга Путеводитель для влюблённых в математику, страница 25 – Эдвард Шейнерман

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

Начнем с укладки квадратов и домино. Вообразим длинную горизонтальную рамку размерами 1 × 10. Мы хотим полностью заполнить ее квадратами 1 × 1 и костяшками домино 1 × 2, не оставив ни единой щели. Вот картинка:

Для удобства обозначим число вариантов F₁₀. Перебирать их все и потом пересчитывать – тяжелый труд, чреватый ошибками. Гораздо лучше упростить задачу.

Не будем с места в карьер искать F₁₀, начнем с F₁. Это проще простого! Нам нужно заполнить рамку 1 × 1 квадратами 1 × 1 и костяшками домино 1 × 2. Домино не поместится, остается единственное решение: взять один квадрат. Другими словами, F₁ = 1.

Теперь разберемся с F₂. Размер рамки 1 × 2. Можно заполнить ее двумя квадратами или одной костяшкой домино. Таким образом, есть два варианта, и F₂ = 2.

Дальше: сколькими способами можно заполнить рамку 1 × 3? Первый вариант: три квадрата. Два других варианта: одна костяшка домино (две не влезут) и квадрат слева или справа. Итак, F₃ = 3.

Еще один шаг: возьмем рамку 1 × 4. На рисунке показаны все варианты заполнения:

Мы нашли пять возможностей, но где гарантия, что мы ничего не упустили? Есть способ проверить себя.

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

Допустим, слева квадрат. Оставшуюся часть нужно заполнить квадратами и домино. Другими словами, нужно заполнить рамку 1 × 3. Это дает 3 варианта, так как F₃ = 3.

Если слева домино, размер оставшейся части 1 × 2, и заполнить ее можно двумя вариантами, так как F₂ = 2.

Таким образом, у нас есть 3 + 2 = 5 вариантов, и мы удостоверились, что F₄ = 5.

Теперь ваша очередь. Подумайте пару минут и найдите все варианты заполнения для рамки 1 × 5. Их немного. Решение – в конце главы. Можете отвлечься и подумать.

Вернемся к нашим квадратам. Хочется верить, что вы нашли 8 вариантов, так как есть 5 способов укладки, где слева квадрат, и еще 3 способа, где слева домино. Таким образом, F₅ = 8.

Подытожим. Мы обозначили F_N количество способов заполнения рамки 1 × n квадратами и костяшками домино. Нам необходимо найти F₁₀. Вот что мы уже знаем:

Двигаемся дальше. Чему равно F₆? Можно нарисовать все варианты, но это скучно. Лучше разобьем вопрос на две части. Сколькими способами можно заполнить рамку 1 × 6, если слева (a) квадрат и (b) костяшка домино? Хорошая новость: мы уже знаем ответ!

В первом случае нам остается пять квадратов, а мы знаем, что F₅ = 8. Во втором случае нужно заполнить четыре квадрата; нам известно, что F₄ = 5. Таким образом, F₅ + F₄ = 13.

Чему равно F₇? Исходя из тех же соображений, F₇ = F₆ + F₅ = 13 + 8 = 21. А как насчет F₈? Очевидно, F₈ = F₇ + F₆ = 21 + 13 = 34. И так далее. Мы обнаружили следующую взаимосвязь:

Еще несколько шагов – и мы найдем искомое число F₁₀. Правильный ответ – в конце главы.

Числа Фибоначчи

Числа Фибоначчи – это последовательность:

Она выстраивается по таким правилам:

– первые два числа 1 и 1;

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

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

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

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

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

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

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