Задача о размножении кроликов

Одним из наиболее известных математиков эпохи Средневековья по праву считается Леонардо Пизано Фибоначчи. Позже мы расскажем о Фибоначчи и его роли в развитии западноевропейской математики более подробно. По иронии судьбы Фибоначчи, который внес выдающийся вклад в развитие математики, стал известным в современной математике только лишь как автор интересной числовой последовательности, называемой числами Фибоначчи. Эта числовая последовательность была получена Фибоначчи при решении знаменитой "задачи о размножении кроликов". Формулировка и решение этой задачи считается основным вкладом Фибоначчи в развитие комбинаторики. Именно с помощью этой задачи Фибоначчи предвосхитил метод рекуррентных соотношений, который считается одним из мощных методов решения комбинаторных задач. Рекуррентная формула, полученная Фибоначчи при решении этой задачи, считается первой в истории математики рекуррентной формулой.

Существо своей "задачи о размножении кроликов" Фибоначчи сформулировал предельно просто:

"Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Возникает вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?"




Для решения этой задачи, которая наглядно демонстрируется с помощью рисунка, обозначим через A пару зрелых кроликов, а через B - пару новорожденных кроликов. Тогда процесс "размножения" может быть описан с помощью двух "переходов", которые описывают ежемесячные превращения кроликов в процессе размножения:

(1)
(2)

Заметим, что переход (1) моделирует ежемесячное превращение каждой зрелой пары кроликов А в две пары, а именно в ту же самую пару зрелых кроликов А и новорожденную пару кроликов В. Переход (2) моделирует процесс "созревания" кроликов, когда новорожденная пара кроликов В через месяц превращается в зрелую пару А. Тогда, если мы начнем в первом месяце со зрелой пары А, тогда процесс размножения кроликов может быть представлен с помощью Таблицы 1.

Таблица 1.

ДатаПары кроликовABA + B
1-го январяA101
1-го февраляAB112
1-го марта ABA213
1-го апреляABAAB325
1-го маяABAABABA538
1-го июняABAABABAABAAB8513

Заметим, что в столбцах А и В таблицы 1 указаны количества зрелых и новорожденных пар кроликов в каждом месяце года, а в таблице А+В - суммарное количество кроликов.

Изучая последовательности А-, В- и (А+В)-чисел, можно установить следующую закономерность в этих числовых последовательностях: каждый член последовательности равен сумме двух предыдущих. Если теперь обозначить n-й член последовательности, удовлетворяющей этому правилу через Fn, тогда указанное выше общее правило может быть записано в виде следующей математической формулы:

Fn = Fn-1 + Fn-2.(3)

Такая формула называется рекуррентной формулой.

Заметим, что конкретные значения числовой последовательности, порождаемой рекуррентной формулой (3), зависят от начальных значений последовательности F1 и F2. Например, мы имеем F1 = F2 = 1 для A-чисел и для этого случая рекуррентная формула (3) "генерирует" следующую числовую последовательность:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... .(4)

Для В-чисел мы имеем: F1 = 0 и F2 = 1; тогда соответствующая числовая последовательность для этого случая будет иметь вид:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .

Наконец, для (А + В)-последовательности мы имеем: F1 = 1 и F2 = 2; тогда соответствующая числовая последовательность для этого случая будет иметь вид:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... .

В математике под числами Фибоначчи, как правило, понимается числовая последовательность (4). Числа Фибоначчи обладают удивительными математическими свойствами, но об этом - на следующей странице нашего Музея.