Задачи, связанные с последовательностью Фибоначчи

1. Числа Фибоначчи появляются в вопросах, связанных с исследованием путей в различных геометрических конфигурациях. Рассмотрим сеть путей, изображённую на рисунке (такую сеть в математике принято называть ориентированным графом), и подсчитаем число путей, которыми можно, двигаясь вдоль стрелок, перейти из вершины А или вершины В в вершину .

Обозначим числа таких путей . Ясно, что при начале движения, как из точки А, так и из точки В, в вершину можно попасть двумя способами: через вершину с последующим шагом вдоль наклонного ребра и через вершину с последующими шагом вдоль горизонтального ребра.

Значит a_n = a_n—1 + a_{n – 2} , b_n = b_n—1 + b_{n – 2} .

Остаётся заметить, что a₁ = 1 = a₂ и b₁ = 1 = b₂ , т. е. количество путей соответствует числам Фибоначчи. Также встречаются задачи не на подсчёт путей, а на выбор рационального перехода по путям – это различные игровые задачи, в которых числа Фибоначчи либо играют роль координат узловых точек ориентированного графа, либо помогают выстроить последовательность.

Задача

«Имеется 76 карточек, на которых написаны разные числа. Эти карточки разложены на столе по кругу числом вниз. Надо найти какие-нибудь три идущие подряд карточки такие, что число, написанное на средней из этих трёх карточек, больше, чем на двух соседних. Перевернут можно последовательно не более 10 карточек. Как надо действовать, чтобы наверняка найти три карточки, для которых выполняется указанное условие?»

Решение:

Для построения рассуждений нам потребуется последовательность Фибоначчи:

1; 1; 2; 3; 5; 8; 13; 21; …

a_n = a_n—1 + a_{n – 2 ,} а₁ = а₂ = 1.

Число карточек 76 = 21 + 21 + 34. (т. е. можно будет использовать данную закономерность)

Пусть N карточек расположены по кругу в вершинах N – угольника.

Если a, b – карточки, то (a; b) – «a лежит раньше b по часовой стрелке».

Дуга (a; b) – промежуток между a и b.

Длина дуги (a; b) – число сторон N – угольника между a и b.

Назовём тройкой ранга k три открытые (числом вверх) карточки (a; b; c), удовлетворяющие условиям:

1. на дугах (a; b) и (b; с) нет открытых карточек;

2. длины дуг (a; b) и (b; с) либо обе равны x_k, либо одна - x_k, а вторая –

x_k+1;

3. число на карточке bбольше числа на карточкеаи с.

В нашей задаче надо найти тройку ранга 1.

Посмотрим, как из тройки ранга kполучить тройку ранга 1.

Пусть тройка (a; b; c) – тройка ранга k .

1 случай: длина обеих дуг (a; b) и (b; с) равны x_k.

На дуге (a; b) откроем точку d так, что длины дуг (a; d) и (d; b) равны x_k-2 и

x_k-1 соответственно. При этом возможны два варианта:

а) d < b ⟹ (d; b; c) – тройка ранга k – 1;

б) d > b ⟹ (a; d; b) – тройка ранга k – 2.

2 случай: Длина дуги (a; b) - x_k+1 (для определённости), а дуги (b; с) - x_k.

На большей дуге откроем точку d так, что длины дуг (a; d) и (d; b) равны x_k x_k-1.

Возможны два варианта:

а) d < b ⟹ (d; b; c) – тройка ранга k – 1;

б) d > b ⟹ (a; d; b) – тройка ранга k – 1.

Применяя последовательно (в обоих случаях) этот способ мы получим тройку

ранга 1, открыв при этом не более k – 1карточки.

Остаётся для решения найти какую-нибудь тройку ранга k.

В нашем случае: N = 76 = 21 + 21 + 34 = 2 x_k + x_k+1.

И всего (с начальными a; b и с нам предстоит открыть k + 2числа, т. е. в

нашем случае – 10 чисел).

Ответ: для нахождения данной тройки чисел достаточно открыть 10 карточек.

3. Задача – шутка

«Докажем», что 64 = 65».

Возьмём для этого квадрат со стороной 8 и разрежем его на части, как показано на рисунке.

Эти части мы сложим в прямоугольник со сторонами 13 и 5, т. е. с площадью, равной 65.

Объяснение этому, на первый взгляд загадочному, явлению найти нетрудно. Всё дело в том, что точки A, B, C и D на самом деле не лежат на одной прямой, а являются вершинами параллелограмма, площадь которого как раз и равна «лишней» единице.

Это правдоподобное, но неверное «доказательство» заведомо ложного высказывания (такие «доказательства» ещё называют «софизмами»), можно проделать ещё более наглядно и «убедительно», если взять вместо квадрата со стороной 8 квадрат со стороной, равной некоторому числу Фибоначчи с достаточно большим номером, a_n. Разобьём этот квадрат на части (см. рисунок) и сложим из этих частей прямоугольник. «Пустота» в виде параллелограмма, вытянутого вдоль диагонали прямоугольника, имеет площадь, равную единице. Наибольшая ширина этой щели, т. е. высота параллелограмма, равна, как легко вычислить,

.

Поэтому, если мы возьмём квадрат со стороной 21 см и «превратим» его в прямоугольник со сторонами 34 и 13 см, то наибольшая ширина щели получится

≈ 0,4 мм, что почти незаметно для глаза.