Теория чисел Фибоначчи (стр. 11 из 14)
Рис. 13.
У трутня один дед и одна бабка, один прадед и две прабабки, два прапрадеда и три прапрабабки. И вообще, как легко установить по индукции, у него ровно Fn+1 праn-дедушек и Fn+2 праn-бабушек.
Числа Фибоначчи часто обнаруживаются в природе – возможно, по причинам, аналогичным закону образования родословного дерева пчел. К примеру, семечки, плотно набитые в крупную "корзинку" обыкновенного подсолнуха, располагаются по спиралям – обычно это 34 спирали, закручивающиеся в одном направлении, и 55 спиралей – в другом. Корзинки поменьше будут иметь соответственно 21 и 34, или же 13 и 21 спираль, а однажды в Англии демонстрировался гигантский подсолнух с 89 спиралями одного направления и 144 – другого. Подобные закономерности обнаруживаются и в некоторых видах сосновых шишек.
Еще рассмотрим пример другого рода. Предположим, что друг на друга наложены две стеклянные пластинки. Сколько существует способов аn прохождения луча света через пластинки или отражения от них после изменения его направления № раз? Несколько первых случаев таковы (см. рис. 14):
а0 = 1 а1 = 2 а2 = 3 а3 = 5
Рис. 14.
Когда № четно, получается четное число преломлений, и луч проходит насквозь; когда же № нечетно, луч отражается и выходит с той стороны, с которой и вошел. По-видимому, аn будут числами Фибоначчи и непродолжительное разглядывание рисунка показывает почему: при № ≥ 2 преломляющиеся № раз лучи либо претерпевают свое первое отражение от внешней поверхности и продолжают прохождение an-1 способами, либо начинают с отражения от внутренней поверхности и затем снова отражаются в обратном направлении, чтобы закончить прохождение an-2 способами. Таким образом, получается фибоначчиева рекуррентность an = an-1 + an-2.Начальные условия отличаются, но не очень, поскольку а0 = 1 = F2 и а1 = 2 = F3; следовательно, все просто сдвигается на два, так что au = Fu+2.
После демонстрации элементарных задач нужно кратко рассказать об истории изучения чисел Фибоначчи, напомнить, что эти числа ввел в 1202 г. Леонардо Фибоначчи, и математики постепенно стали выяснять все больше и больше интересного о них. Например, Эдуард Люка, причастный к головоломке о ханойской башне, активно занимался ими во второй половине девятнадцатого столетия (в действительности, благодаря именно Люка, название "числа Фибоначчи" стало общеупотребительным). Одно из его удивительных достижений состояло в использовании свойств чисел Фибоначчи для доказательства того, что 39-значное число Мерсенна 2127 – 1 является простым.
После первого знакомства с числами Фибоначчи имеет смысл поговорить о проявлениях свойств чисел Фибоначчи в природе, искусстве, науке и технике. Здесь же нужно сформулировать понятие "золотого сечения" и на примерах проиллюстрировать все разнообразие ситуаций, в которых оно обнаруживается. Данная тема воспринимается школьниками обычно очень эмоционально, и это надо использовать, чтобы закрепить интерес к ее изучению и к изучению математики вообще.
После этого можно выбрать одно или несколько направлений, которые будут изучаться более подробно. Выигрышным вариантом следует признать изучение рекуррентных соотношений. В рамках данной темы возможны отклонения в самых различных направлениях. Многообразие задач здесь тоже очень велико. И ценно также то, что в процессе изучения темы выстраивается стройная теория рекуррентных соотношений. Т. е. учащиеся знакомятся с цельной теорией, имеющей множество приложений. Используемые же при этом методы достаточно элементарны и доступны для понимания. При этом охватываются многие разделы комбинаторики.
На уроках информатики стоит решить несколько комбинаторных задач и написать для них программы, вычисляющие неизвестные значения. Можно поэкспериментировать с нахождением времени, необходимого машине на вычисление тех или иных чисел.
5.2. Решение задач
При решении многих комбинаторных задач школьники часто пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere – возвращаться). Пользуясь рекуррентным соотношением, можно свести задачу об № предметах к задаче об № – 1 предметах, потом к задаче об № – 2 предметах и т. д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного соотношения явную формулу для решения комбинаторной задачи.
Например, так можно вывести формулу Рn = n! для числа перестановок № элементов с помощью формулы для числа размещений без повторений. Но ту же формулу можно вывести и иначе, найдя сначала рекуррентное соотношение, которому удовлетворяет Рn.
Пусть у нас есть № предметов a1,..., an-1, an. Любую их перестановку можно получить так: взять некоторую перестановку предметов a1,..., an-1 и присоединить к ней элемент аn. Ясно, что элемент аn может занять различные места. Его можно поставить в самое начало, между первым и вторым элементами перестановки, между вторым и третьим, можно поставить и в самый конец. Число различных мест, которые может занять элемент аn, равно n, и потому из каждой перестановки элементов a1,..., an-1 получается № перестановок элементов a1,..., an-1, an. Но это означает, что перестановок из № элементов в № раз больше, чем перестановок из № – 1 элементов. Тем самым установлено рекуррентное соотношение:
Рn = № Рn-1.
Пользуясь этим соотношением, последовательно выводим, что:
Рn = № Рn-1 = № (n-1) Рn-2 = № (n-1) … 2Р1.
Но Р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) называют числами Фибоначчи. Они обладают целым рядом замечательных свойств. Сейчас мы выведем выражение этих чисел через комбинаторные коэффициенты Ckm. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.
Найти число n-последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.
Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию" – сама пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца, "дед" – в конце 5-го месяца и "прадед" – в конце второго месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд – только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.
Установленная связь показывает, что число n-последовательностей, обладающих указанным свойством, равно F(n).
Докажем теперь, что
F(n) =
+ C1n + +... + , (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).