Дана головоломка була придумана великим італійським вченим-математиком Фібоначчі, який жив в XIII столітті. Леонардо Пізанський (лат. Leonardo Pisano, близько 1170-1250, Піза), більш відомий світові під прізвиськом Фібоначчі. Рекурентна формула, яку отримав автор завдання вирішуючи свою ж задачу, вважається першою рекурентною формулою в історії математики. Також в цьому завданні використані відомі багатьом числа Фібоначчі.
Кролики Фібоначчі
Умови задачі:
«В обгороджене місце поміщені пара кроликів (самка і самець) 1 січня. Ця пара кроликів починає приносити потомство через місяць, чи то пак з 1 лютого і дає приплід щомісяця по парі нових кроликів. Кожна нова пара кроликів стає статевозрілою рівно через місяць і теж починає приносити щомісяця по парі кроликів.
Питання: скільки всього кролів буде через рік, чи то пак через 12 місяців з початку розмноження?»
Рішення завдання:
Для спрощення рішення задачі позначимо через A пару зрілих кроликів, через B — пару новонароджених кроликів. Тоді процес "розмноження" може бути описаний за допомогою двох «переходів», які відбивають щомісячні перетворення кроликів в процесі розмноження:
А=>AB
B=>A
А=>AB позначає перетворення однієї дорослої пари в повноцінну сім'ю, тобто народження ще пари кроликів.
B=>A — перехід молодняку в зрілий вік.
- 1 місяць (січень) — А (1 пара молодняк)
- 2 місяць (лютий) — АВ (1 пара зріла + 1 пара молодняк)
- 3 місяць (березень) — АВА (2 пари зрілі + 1 пара молодняк)
- 4 місяць (квітень) — АВААВ (3 пари зрілі + 2 пари молодняк)
- 5 місяць (травень) — ABAABABA (5 пар зрілі + 3 пари молодняк)
Уважно вивчивши послідовності чисел А, В і А + В, бачимо закономірність: кожен член послідовності дорівнює сумі двох попередніх. Позначимо кількість пар кроликів через С, а через d — порядковий номер місяця. Складаємо формулу:
Cd = Cd-1 + Cd-2
Називається вона — рекурентна формула.
За допомогою отриманої формули розраховуємо кількість кроликів по місяцях
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Це так звані числа Фібоначчі — послідовність чисел, де кожне наступне число, починаючи з третього, виходить складанням двох попередніх чисел.