Fibonacci's Rabbits
The puzzle
A pair of newborn rabbits is put in a field. A pair becomes fertile at one month old and from then on produces a new pair every month. No rabbit dies.
How many pairs are in the field after twelve months?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Count the pairs month by month: 1, 1, 2, 3, 5 …
Hint 2
This month's pairs are last month's pairs plus the ones born - and the ones born are exactly the pairs that existed the month before.
Show the answer Hide the answer
144 pairs.
How to get there
Every pair alive last month is still alive, and every pair alive the month before that is now old enough to have produced one new pair. So F(n) = F(n-1) + F(n-2).
Starting from 1, 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. The twelfth month gives 144 pairs.
This is where the Fibonacci numbers come from - Leonardo of Pisa posed exactly this question in 1202. The ratio of consecutive terms settles towards 1.618, the golden ratio, which is why the sequence turns up in places that have nothing to do with rabbits.
The technique worth keeping
Translate the breeding rule into a statement about counts and the recurrence writes itself. "What is here next month" is usually "what is here now, plus what the rule adds", and the rule tells you which earlier term that addition depends on.