FIBONACCI AND THE FROG
by Albert FRANK, Erik GOOLAERTS, Catherine MARCANDELLA
Introduction:
Among the puzzles of the quarter finals 2001 of the "Championnat Inernational des Jeux Mathématiques et Logiques", organised by the FFJM (Fédération française des jeux mathématiques), the next question was asked:
A small frog has to travel from point A to point B. Between A and B are situated twenty tiles (A and B are not considered as a tile). The little frog must at all times jump forward, and can jump immediately from point A to point B. She may also land on one or more tiles. However, she can never make use of two consecutive tiles on her way from A to B (jumping from A to the first tile is allowed, as is jumping from the last tile to B). In how many ways can the little frog travel from A to B?
A complete elaboration of this formula is not necessary for our purpose. Indeed a more elegant approach (which is explained in the appendix) shows that the solution to this puzzle is also given by the 22nd number of Fibonacci. The equivalence of these two approaches (see properties * of the Fibonacci numbers) serves as proof.
The Fibonacci numbers are constructed as follows: F1 = F2 = 1
Then by recurrence the other numbers are found: Fn = Fn-2 + Fn-1
Who was Leonardo Fibonacci?
An Italilan mathematician, also known as Leonardo of Pisa, born in 1170 in the town of Pisa (one of the major commercial centres in Italy, in those times of the same importance as Venice and Genoa). He studied the algebraic publications of Al-Khuwarizmi. Afterwards Fibonacci travelled the entire mediterranean world, meeting numerous scientists and studying different systems of arithmetic used at the time. After his return to Pisa, he published in 1202 his manuscript Liber Abbaci, presenting the Indo-Arabe way of numbering and comparing it to the Roman system. He was the first great mathematician in the scientific world to adopt this system and vulgarise it. His work also contains most of the results discovered by the Arabs in algebra and arithmetics (square roots, cubic roots, linear and quadratic equeations). In 1220 he published Practica Geometriae, which summed up all the knowledge in geometry and trigonometry in those days. Fibonacci also continues his own research. He is at the origin, among other things, of the solution of famous problems: to find a number x in order that x2 + 5 and x2 - 5 are both square numbers; solve the cubic equation x3 + 2 x2 + 10 x = 20.These and other problems of the same nature are published in his Liber Quadratorum (1225). Fibonacci is also at the origin of the series that carries his name, of which the first two numbers are equal to 1, and the n-th number (n>2) is the sum of the two preceding numbers in the series. This series has a great number of properties. Among the best known are:
- The sums of the "diagonals" of the Pascal triangle result in the Fibonacci numbers (which explains the equivalence between the two solutions - formula (1) or the 22-nd numbers of Fibonacci) (*)
- The n-th Fibonacci number is prime if n is prime or n = 4.
- The sum of ten consecutive Fibonacci numbers equals the product of the seventh number by eleven.
- The sum of the squares of the Fibonacci numbers of n-th and (n+1)-th order is equal to the Fibonacci number of order 2n+1.
Generalisation of the problem:
The generalisation of the problem involves two parameters: the number of tiles and the restrictions placed on the movements of the frog. Instead of not being allowed to land on two consecutive tiles, the condition can be omitted or changed to jumping over a minimum of k free tiles with each jump (jumping from A to any tile is still allowed, as is jumping from any tile to B, since A and B are not considered as tiles).
Under the initial condition (the frog can't land on two consecutive tiles), the generalisation of the problem to n tiles immediately becomes: the possible number of different ways to travel from A to B is given by the (n+2)-th Fibonacci number. It's also possible to generalise the formula (1), distinguishing
between even and odd numbers of tiles.
Let's examine the general problem : we have n tiles and the frog has to jump over at least K tiles between two stops (K > 0).
K = 0 The number of possible ways equals 2n
K = 1 The number of possible ways equals Fn+2
K = 2 Let's make the recurrent series :
K = 3 Lets make the recurrent series :
V1 = V2 = V3 = V4 = 1
Vn = Vn-1 + Vn-4 The number of possible ways equals Vn+4
K any given number (<n) Lets make the recurrent series :
If the frog has to jump over at least K tiles between two stops, this proportion (rapidly) converges as n becomes higher.
Experimentally we noticed that the value of this ratio is given by the highest positive real root of the equation xK+1 - xK - 1 = 0. A general solution to this equation has still to be found. Here are some results :
Conclusion :
As so often happens, commencing from a nice puzzle about a little frog that jumps from A to B, some unexpected developments have presented themselves. And once again it's remarkable that Fibonacci shows up.
Appendix : Direct approach of the problem (drawn up by Catherine).
1. The frog can't land on two consecutive tiles (as put in the basic problem). The number of tiles is a parameter of the problem.
The Fibonacci numbers appear.
2. The frog has to jump over at least two free tiles. The number of tiles is a parameter again.
Now we find a series where you don't add up the two preceding numbers, but skip one: add the preceding and third preceding number.
3. The frog has to jump over at least 3 free tiles between two landings. The number of tiles is a parameter.
Here we find a series where you don't add up the two preceding numbers, but skip two: add the preceding and fourth preceding number.
4. The frog has no restrictions.
And we find the positive powers of 2.