Общие методические указания

Начинать изучение чисел Фибоначчи следует с демонстрации их естественного появления во многих задачах и ситуациях. Помимо классической задачи о кроликах необходимо сформулировать и другие задачи, в которых появляются числа Фибоначчи.

Наглядный пример естественного возникновения чисел Фибоначчи дают, например, так называемые "родословные деревья пчел" Рассмотрим родословную пчелы-самца. Каждый самец (называемый также трутнем) появляется на свет непарным путем от самки (называемой также маткой), однако каждая самка имеет двух родителей – самца и самку. Несколько начальных уровней такого дерева представлены ниже на рисунке 13.

Рис. 13.

У трутня один дед и одна бабка, один прадед и две прабабки, два прапрадеда и три прапрабабки. И вообще, как легко установить по индукции, у него ровно F_n+1 праⁿ-дедушек и F_n+2 праⁿ-бабушек.

Числа Фибоначчи часто обнаруживаются в природе – возможно, по причинам, аналогичным закону образования родословного дерева пчел. К примеру, семечки, плотно набитые в крупную "корзинку" обыкновенного подсолнуха, располагаются по спиралям – обычно это 34 спирали, закручивающиеся в одном направлении, и 55 спиралей – в другом. Корзинки поменьше будут иметь соответственно 21 и 34, или же 13 и 21 спираль, а однажды в Англии демонстрировался гигантский подсолнух с 89 спиралями одного направления и 144 – другого. Подобные закономерности обнаруживаются и в некоторых видах сосновых шишек.

Еще рассмотрим пример другого рода. Предположим, что друг на друга наложены две стеклянные пластинки. Сколько существует способов а_n прохождения луча света через пластинки или отражения от них после изменения его направления № раз? Несколько первых случаев таковы (см. рис. 14):

а₀ = 1 а₁ = 2 а₂ = 3 а₃ = 5

Рис. 14.

Когда № четно, получается четное число преломлений, и луч проходит насквозь; когда же № нечетно, луч отражается и выходит с той стороны, с которой и вошел. По-видимому, а_n будут числами Фибоначчи и непродолжительное разглядывание рисунка показывает почему: при № ≥ 2 преломляющиеся № раз лучи либо претерпевают свое первое отражение от внешней поверхности и продолжают прохождение a_n-1 способами, либо начинают с отражения от внутренней поверхности и затем снова отражаются в обратном направлении, чтобы закончить прохождение a_n-2 способами. Таким образом, получается фибоначчиева рекуррентность a_n = a_n-1 + a_n-2.Начальные условия отличаются, но не очень, поскольку а₀ = 1 = F₂ и а₁ = 2 = F₃; следовательно, все просто сдвигается на два, так что a_u = F_u+2.

После демонстрации элементарных задач нужно кратко рассказать об истории изучения чисел Фибоначчи, напомнить, что эти числа ввел в 1202 г. Леонардо Фибоначчи, и математики постепенно стали выяснять все больше и больше интересного о них. Например, Эдуард Люка, причастный к головоломке о ханойской башне, активно занимался ими во второй половине девятнадцатого столетия (в действительности, благодаря именно Люка, название "числа Фибоначчи" стало общеупотребительным). Одно из его удивительных достижений состояло в использовании свойств чисел Фибоначчи для доказательства того, что 39-значное число Мерсенна 2¹²⁷ – 1 является простым.

После первого знакомства с числами Фибоначчи имеет смысл поговорить о проявлениях свойств чисел Фибоначчи в природе, искусстве, науке и технике. Здесь же нужно сформулировать понятие "золотого сечения" и на примерах проиллюстрировать все разнообразие ситуаций, в которых оно обнаруживается. Данная тема воспринимается школьниками обычно очень эмоционально, и это надо использовать, чтобы закрепить интерес к ее изучению и к изучению математики вообще.

После этого можно выбрать одно или несколько направлений, которые будут изучаться более подробно. Выигрышным вариантом следует признать изучение рекуррентных соотношений. В рамках данной темы возможны отклонения в самых различных направлениях. Многообразие задач здесь тоже очень велико. И ценно также то, что в процессе изучения темы выстраивается стройная теория рекуррентных соотношений. Т. е. учащиеся знакомятся с цельной теорией, имеющей множество приложений. Используемые же при этом методы достаточно элементарны и доступны для понимания. При этом охватываются многие разделы комбинаторики.

На уроках информатики стоит решить несколько комбинаторных задач и написать для них программы, вычисляющие неизвестные значения. Можно поэкспериментировать с нахождением времени, необходимого машине на вычисление тех или иных чисел.

Решение задач

При решении многих комбинаторных задач школьники часто пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere – возвращаться). Пользуясь рекуррентным соотношением, можно свести задачу об № предметах к задаче об № – 1 предметах, потом к задаче об № – 2 предметах и т. д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного соотношения явную формулу для решения комбинаторной задачи.

Например, так можно вывести формулу Р_n = n! для числа перестановок № элементов с помощью формулы для числа размещений без повторений. Но ту же формулу можно вывести и иначе, найдя сначала рекуррентное соотношение, которому удовлетворяет Р_n.

Пусть у нас есть № предметов a_1,..., a_n-1, a_n. Любую их перестановку можно получить так: взять некоторую перестановку предметов a_1,..., a_n-1 и присоединить к ней элемент а_n. Ясно, что элемент а_n может занять различные места. Его можно поставить в самое начало, между первым и вторым элементами перестановки, между вторым и третьим, можно поставить и в самый конец. Число различных мест, которые может занять элемент а_n, равно n, и потому из каждой перестановки элементов a_1,..., a_n-1 получается № перестановок элементов a_1,..., a_n-1, a_n. Но это означает, что перестановок из № элементов в № раз больше, чем перестановок из № – 1 элементов. Тем самым установлено рекуррентное соотношение:

Р_n = № Р_n-1.

Пользуясь этим соотношением, последовательно выводим, что:

Р_n = № Р_n-1 = № (n-1) Р_n-2 = № (n-1) … 2Р₁.

Но Р_n = l, так как из одного элемента можно сделать лишь одну перестановку. Поэтому:

Р_n = № (n-1) … 2 1 = n!.

Таким образом, мы снова получили формулу Р_n = n!.

Много рекуррентных соотношений встречалось нам при решении задач на разбиения, задач о фигурах на шахматной доске и т. д. Сейчас мы рассмотрим еще несколько таких задач, а в заключение остановимся на общей теории рекуррентных соотношений.

Задача о кроликах: Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Решение: Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут н исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.

Обозначим через F(n) количество пар кроликов по истечении № месяцев с начала года. Мы видим, что через № + 1 месяцев будут эти F(n) пар и еще столько новорожденных пар кроликов, сколько было в конце месяца № – 1, то есть еще F(n – 1) пар кроликов. Иными словами, имеет место рекуррентное соотношение:

F(n + l) = F(n) + F(n – l). (35)

Так как, по условию, F(0) = 1 и F(1) = 2, то последовательно находим:

F(2) = 3, F(3) = 5, F(4) = 8 и т. д.

В частности, F(12) =377.

Числа F(n) называют числами Фибоначчи. Они обладают целым рядом замечательных свойств. Сейчас мы выведем выражение этих чисел через комбинаторные коэффициенты C^k_m. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

Найти число n-последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.

Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию" – сама пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца, "дед" – в конце 5-го месяца и "прадед" – в конце второго месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000.

Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд – только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.

Установленная связь показывает, что число n-последовательностей, обладающих указанным свойством, равно F(n).

Докажем теперь, что

F(n) = + C¹_n + +... + , (36)

где р = (n+1)/2, если № нечетно, и р = n/2, если № четно.

Иными словами, р – целая часть числа (n+1)/2 – (в дальнейшем мы будем обозначать целую часть числа α χерез E(α); ςаким образом, р = E [(n+1)/2].

В самом деле, F(n) – это число всех n-последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно k единиц и № – k нулей, равно . Так как при этом должно выполняться неравенство k ≤ № – k + 1, то k изменяется от 0 до E [(n+1)/2]. Применяя правило суммы, приходим к соотношению (36).

Равенство (36) можно доказать и иначе. Положим:

G (n) = + C¹_n + +... + ,

где р = E [(n+1)/2]. Из равенства = + легко следует, что:

G(n) = G(n – 1) + G(n – 2). (37)

Кроме того, ясно, что G(1)=2 = F(1) и G(2) =3 = F(2).

Так как обе последовательности F(n) и G(n) удовлетворяют рекуррентному соотношению Х(n) =Х(n – 1) + X (n – 2), то имеем:

G(3) = G(2) + G(1) = F(2) + F(l) = F(3),

и, вообще, G(n)=F(n).

Приведем и другой метод доказательства.

Мы непосредственно установили связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно было установить и иначе, непосредственно доказав, что число Т(n) решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению:

T(n+1) = T(n) + T(n – 1), (38)

что и числа Фибоначчи.

В самом деле, возьмем любую (n-1)-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим n-последовательность, удовлетворяющую нашему условию. Обратно, если взять любую n-последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим (n+1)-последовательность с тем же свойством. Мы доказали, что число "хороших" последовательностей, оканчивающихся на нуль, равно Т(n).

Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1 (n – 1)-последовательность может быть любой, лишь бы в ней не шли подряд две единицы.

Поэтому число "хороших" последовательностей, оканчивающихся единицей, равно Т(n – 1). Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что Т(n + 1) = Т(n) + Т(n – 1).

Мы получили, таким образом, то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа Т(n) и F(n) совпадают.

Чтобы доказать совпадение чисел Т(n) и F(n), надо еще показать, что T(n)=F(n) и T(2) – F(2) – тогда уже в силу рекуррентного соотношения имеем и T(3)=F(3), T(4)=T(4) и т. д. Существуют две 1-последовательности, удовлетворяющие поставленному условию: 0 и 1, и три 2-последовательности; 00, 01 и 10.

Поэтому T(1) = 2 = F(1) и T(2) =3 =. F(2). Тем самым утверждение доказано.

Для решения комбинаторных задач часто применяют метод, использованный выше. Устанавливают для данной задачи рекуррентное соотношение и показывают, что оно совпадает с рекуррентным соотношением для другой задачи, решение которой нам уже известно. Если при этом совпадают и начальные члены последовательностей в достаточном числе (позже мы остановимся подробнее на том, сколько членов должны совпадать), то обе задачи имеют одинаковые решения.

Применим описанный прием для решения следующей задачи.

Задача. Пусть дано некоторое множество из № предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй (то есть, скажем, одна часть состоит из элементов от первого до m-го, а вторая – из элементов от (m + 1)-го до n-го). После этого каждую из частей таким же образом разобьем на две непустые части (если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям). Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам)?

Решение: Обозначим число способов разбиения для множества из n+1 предметов через В_n. На первом шагу это множество может быть разбито № способами (первая часть может содержать один предмет, два предмета,..., и предметов). В соответствии с этим множество всех процессов разбиений распадается на № классов – в s-й класс входят процессы, при которых первая часть состоит из s предметов.

Подсчитаем число процессов в s-м классе. В первой части содержится s элементов. Поэтому ее можно разбивать далее B_s-1 различными процессами. Вторая же часть содержит № – s+1 элементов, и ее можно разбивать далее B_n-s процессами. По правилу произведения получаем, что s-й класс состоит из B_s-1B_n-s различных процессов. По правилу суммы отсюда вытекает, что:

B_n = B₀ B_n-1 + B₁ B_n-2 + … + B_n-1 B₀ (39)

Мы получили рекуррентное соотношение для B_n. Этому соотношению удовлетворяют числа:

Т_n =

Чтобы доказать равенство

В_n = Т_n = . (40)

нам осталось показать, что начальные члены Т₀ и В₀ последовательностей T₀, T₁,..., T_n, … и В₀, В₁,..., В_n,... совпадают.

Мы имеем T₀ = =1. С другой стороны, В₀ = 1, так как множество из одного элемента можно разделить единственным образом. Итак, В₀ = T_0.Но по рекуррентной формуле имеем В₁ = =1.Так как T₀ удовлетворяет той же рекуррентной формуле, то T₁ = = 1.Далее устанавливаем, что:

B₂ = B₀ B₁ + B₁ B₀ = 2 и T₂ = T₀ T₁ + T₁ T₀ = 2 и т. д.

Итак, все члены обеих последовательностей совпадают. Таким образом, доказан следующий результат:

Число процессов последовательного деления множества из № + 1 элементов, расположенных в некотором порядке, равно:

Т_n = .