Магия математики. Как найти x и зачем это нужно

Мы заглянули лишь в замочную скважину той двери, за которой раскинулся сад самых настоящих чудес. Только растут в нем не деревья, а числовые закономерности, уходящие корнями в последовательность Фибоначчи. И вам, наверняка, не терпится узнать, для чего еще, кроме подсчета поголовья кроликов, нужны эти числа. На самом деле – много для чего. В 1150 году (задолго до того, как Леонардо Пизанский представил миру задачку про кроликов) индийский поэт Хемачандра задался очень интересным вопросом: сколькими способами можно сложить стихотворную стопу из n безударных или ударных слогов. Давайте сперва переведем эту проблему из плоскости поэзии в плоскость математики.

Вопрос: Сколькими способами можно записать число n как сумму единиц и двоек?

Ответ: Обозначим результат как f_n. Вот что будем иметь при стартовых значениях n:

У нас есть один вариант, дающий в сумме 1, два варианта, дающих 2 (1 + 1 и 2), и три варианта, дающих 3 (1 + 1 + 1, 1 + 2 и 2 + 1). Повторимся: для получения нужной нам суммы доступны только единицы и двойки. При этом порядок этих цифр имеет значение: 1 + 2 и 2 + 1 суть две разные комбинации. Получить 4 можно уже пятью разными вариантами: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2. По всему выходит, что числа в правой части нашей таблицы – это числа из последовательности Фибоначчи, и так оно есть на деле.

Давайте попробуем понять, почему вдруг 5 можно получить f5 = 8 различными способами. Начинаться сложение может с 1 или 2. Сколько вариантов будет начинаться именно с 1? За первой цифрой должна следовать некая комбинация 1 и 2, которая в сумме даст 4, а по предыдущей строке мы знаем, что таких комбинаций у нас f₄ = 5. Теперь так же посчитаем, сколько вариантов будет начинаться с 2. В этом случае комбинация после первой цифры должна давать нам 3. Смотрим чуть выше по таблице и видим, что f₃ = 3. Значит, общее количество комбинаций 1 и 2, дающих в сумме 5, должно быть 5 + 3 = 8. Тот же алгоритм приведет нас к тому, что для 6 таких комбинаций будет 13: f₅ = 8, начинающихся с 1, плюс f₄ = 5, начинающихся с 2. В целом же, для суммы n их число равно f_n, из которых f_n–1 имеют в начале 1, а f_n–2 – 2. Следовательно,

fn=fn – 1 + fn – 2

Причем все значения f_n дублируют числа последовательности Фибоначчи и будут и дальше их дублировать с увеличением значения n. Причина в том, что это и есть последовательность Фибоначчи, только в несколько измененном виде – с небольшим смещением. Обратите внимание, что f₁ = 1 = F₂, f₂ = 2 = F₃, f₃ = 3 = F₄ и т. д. (для удобства договоримся, что f₀ = F₁ = 1, а f_–1 = F₀ = 0). Обобщая, мы можем утверждать, что при n ≥ 1

f_n=F_n+1

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

Так, восьмая диагональ дает нам

1 + 7 + 15 + 10 + 1 = 34 =F₉

С точки зрения «подсчета комбинаций» это значит, что

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

Вопрос: Сколько существует возможных комбинаций единиц и двоек, дающих в сумме 8?

Ответ номер один: Судя по тому, о чем мы говорили чуть выше, – f₈ = F₉.

Ответ номер два: Представим себе эту проблему как 5 частных задач, в основе каждой из которых лежит количество двоек в комбинации. Сколько комбинаций обойдется вообще без двоек? Разумеется, только одна – 11111111. И поэтому совсем не случайно, что

С одной двойкой? Уже семь: 2111111, 1211111, 1121111, 1112111, 1111211, 1111121, 1111112. Каждая из них состоит из семи цифр, и, смещая двойку шаг за шагом, получаем

С двумя двойками (скажем, 221111)? Не будем перечислять их все, просто отметим, что любая из них будет состоять из двух двоек и четырех единиц, то есть всего из шести цифр, что дает нам возможных местоположений двоек. По той же логике комбинации с тремя двойками будут включать в себя две единицы и состоять из 5 цифр, а общее их количество будет равняться И наконец, из четырех двоек у нас получится всего одна комбинация (а именно 2222), потому что

Оба ответа отлично проясняют всю ситуацию. И заодно объясняют, почему сумма чисел n-ной диагонали треугольника Паскаля равна одному из чисел последовательности Фибоначчи. То есть при n ≥ 0 сложение чисел диагонали n (вплоть до того момента, пока через n/2 шагов мы не выйдем за границы треугольника) дает нам

К тому же можно прийти, представив последовательность Фибоначчи в виде плиток черепицы. Тогда f₄ = 5 означает 5 способов выложить один ряд (условно состоящий из 4 квадратов) одинарными (в виде квадратов) и двойными (в виде прямоугольников) плитками. То есть 1 + 1 + 2 будет выглядеть как «квадрат – квадрат – прямоугольник».