FIBONACCI ET LA GRENOUILLE

^{Albert FRANK, Erik GOOLAERTS, Catherine MARCANDELLA}

Introduction :

Parmi les énoncés des quarts de finale 2001 du Championnat International des Jeux Mathématiques et Logiques de la FFJM (Fédération française des jeux mathématiques), se trouvait l’énoncé suivant :

Une grenouille doit se rendre du point A au point B. Entre A et B se trouvent vingt dalles (A et B ne sont pas considérés comme dalles). La grenouille (qui ne recule jamais) dispose de beaucoup de chemins : soit elle saute directement de A à B, soit elle s’arrête sur une ou plusieurs dalles. Cependant, elle ne peut pas s’arrêter sur deux dalles consécutives. De combien de manières différentes peut-elle se rendre de A à B ?

A  B

Résolution du problème de base :

La solution est donnée par _C = 17.711 (1)

La démonstration de cette formule n’est pas nécessaire. En effet, une approche plus élégante (qui sera développée en annexe) montre que la solution est donnée par le 22ième

nombre de Fibonacci. L’équivalence des deux approches (propriété * des nombres de Fibonacci, page 2) sert de démonstration.

Les nombres de Fibonacci sont donnés par F₁ = F₂ = 1, puis par la récurrence

F_n = F_n-2 + F_n-1

Qui était Leonardo Fibonacci ?

Mathématicien italien, connu aussi sous le nom de Léonard de Pise, il est né en 1170 à Pise (l’un des plus grands centres commerciaux d’Italie, à l’époque, au même rang que Venise et Gênes). Il étudia les travaux algébriques d’al-Khuwarizmi. Par la suite, Fibonacci voyagea dans tout le monde méditerranéen, rencontrant de nombreux scientifiques et prenant connaissance des différents systèmes de calcul en usage à l’époque. De retour à Pise, il publie en 1202 un ouvrage, Liber abbaci , où, le comparant au système romain, il expose le système de numération indo-arabe. Il est le premier grand mathématicien à l’adopter et à le vulgariser auprès des scientifiques. Son ouvrage contient également la plupart des résultats connus des Arabes en algèbre et en arithmétique (racines carrées, racines cubiques, équations du premier et du second degré). En 1220, il publie Practica geometriae , qui recense toutes les connaissances de l’époque en géométrie et en trigonométrie.

Fibonacci poursuivit aussi ses propres travaux. Il est à l’origine, entre autres, de la résolution de problèmes célèbres : trouver un nombre x tel que x² + 5 et x² — 5 soient tous deux des carrés; résoudre l’équation du troisième degré x³ + 2 x² + 10 x = 20). Ces problèmes ainsi que d’autres de même nature se retrouvent dans Liber quadratorum (1225). Fibonacci est à l’origine de la suite récurrente qui porte son nom, suite dont les deux premiers termes sont des 1 et dont le terme d’ordre n est égal à la somme des termes d’ordre n - 1 et n - 2 pour tout n supérieur ou égal à 3.

Cette suite possède un très grand nombre de propriétés extrêmement riches.

Citons , parmi les plus célèbres :

- Les sommes des « diagonales » du triangle de Pascal sont les nombres de Fibonacci (ce qui explique l’équivalence entre les deux solutions - formule 1 ou 22 ième nombre de Fibonacci) -

du problème des sauts de la grenouille. (*)

- Le N ième nombre de Fibonacci est premier si N est premier ou si N = 4.

- La somme de dix nombres consécutifs de Fibonacci est égale au produit par onze du septième terme.

- La somme des carrés des nombres de Fibonacci d’ordre n et n +1 est égale au nombre de Fibonacci d’ordre 2n + 1.

- Le rapport F _n+1 / F _n converge (rapidement) vers le NOMBRE D’OR φ = (1 + ) / 2.

- F_n = [ (1 +)ⁿ - (1 - )ⁿ ] / 2ⁿ (Formule de Binet, 1843)

Généralisation du problème :

La généralisation du problème peut concerner deux paramètres, le nombre de dalles et les contraintes (la grenouille, au lieu de ne pas pouvoir s’arrêter sur deux dalles consécutives, peut soit n’avoir aucune contrainte, soit devoir laisser un nombre minimum k de dalles libres entre deux arrêts).

Avec la contrainte initiale (la grenouille ne peut pas s’arrêter sur deux dalles successives), la généralisation à n pavés est immédiate : le nombre de chemins possibles est donné par le

(n + 2) ième nombre de Fibonacci. (Il est également possible de généraliser la formule (1), en distinguant les cas pairs et impairs.

Examinons maintenant le problème général : n dalles ; la grenouille doit laisser au minimum K dalles libres entre deux arrêts (K ≥ 0).

K = 0 Le nombre de chemins possibles est 2ⁿ.

K = 1 Le nombre de chemins possibles est F _n+2 .

K = 2 Créons la suite récurrente :

M₁ = M₂ = M₃ = 1. M_n = M _n-1 + M _n-3. Le nombre de chemins possibles est M _n+3 .

K = 3 Créons la suite récurrente :

V₁ = V₂ = V₃ = V₄ = 1. V_n = V _n-1 + V _n-4. Le nombre de chemins possibles est V _n+4 .

K quelconque (< n) Créons la suite récurrente :

R₁ = ^… = R _K+1 = 1. R_n = R _n-1 + R _n-K-1 . Le nombre de chemins possibles est R _n+K+1 .

Convergence des rapports R _{n+ K+2} / R _{n+K+1 ,}en fonction du nombre n de dalles :

Pour K dalles au minimum devant rester libre entre deux arrêts de la grenouille, ces rapports convergent (rapidement) lorsque n augmente.

Expérimentalement, nous nous sommes aperçus que la valeur de cette convergence est donnée par la plus grande racine réelle de l’équation x ^K+1 - x ^K - 1 = 0 . Une expression générale de la solution resterait à trouver. Donnons quelques valeurs :

K	Solution de	Valeur du rapport
0	x – 2 = 0	2
1	x ^2 – x – 1 = 0	φ (≈ 1.61803)
2	x ^3 – x ^2 – 1 = 0	≈ 1.46557
3	x ^4 – x ^3 – 1 = 0	≈ 1.38028
5	x^6 – x^5 – 1 = 0	≈ 1.32472
100	x^101 – x^100 – 1 = 0	≈ 1.03457
500	x^501 – x^500 – 1 = 0	≈ 1.0094
→ ∞		→ 1

Conclusion :

Comme c’est souvent le cas, à partir d’un sympathique énoncé sur les sauts d’une grenouille, des développements inattendus se sont présentés. Il est remarquable qu’une fois de plus, Fibonacci soit présent au rendez-vous.

Annexe : Approche directe du problème (trouvé par Catherine).

1. La grenouille ne peut s’arrêter sur deux dalles adjacentes (comme dans le problème de base). Le nombre de dalles est un paramètre.

Nombre de dalles.

x

1 + 1 = 2

(+1 pour le

x

trajet direct)

x

2 +1 = 3

x

x

x

x

x

4 + 1 = 5

x

x

x

x

x

x

x

x

x

x

7 + 1 = 8

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

12 + 1 = 13

La suite de Fibonacci apparaît.

2. La grenouille doit laisser au moins deux dalles libres entre deux arrêts. Le nombre de dalles est un paramètre.

Nombre de dalles.

x

1 + 1 = 2

(+1 pour le

x

trajet direct)

x

2 +1 = 3

x

x

x

3 + 1 = 4

x

x

x

x

x

x

5 + 1 = 6

x

x

x

x

x

x

x

x

x

x

x

8 + 1 = 9

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

12 + 1 = 13

Ici, c’est une suite où il ne faut pas additionner les deux nombres précédents, mais il faut en sauter un.

3. La grenouille doit laisser au moins trois dalles libres entre deux arrêts. Le nombre de dalles est un paramètre.

Nombre de dalles.

x

1 + 1 = 2

(+1 pour le

x

trajet direct)

x

2 +1 = 3

x

x

x

3 + 1 = 4

x

x

x

x

4 + 1 = 5

x

x

x

x

x

x

x

6 + 1 = 7

x

x

x

x

x

x

x

x

x

x

x

x

9 + 1 = 10

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

13 + 1 = 14

Ici, c’est une suite où il ne faut pas additionner les deux nombres précédents, mais il faut en sauter deux.

4. La grenouille n’a aucune contrainte.

Nombre de dalles.

X

1 + 1 = 2

(+1 pour le

X

x

trajet direct)

X

x

3 + 1 = 4

X

x

x

X

x

X

x

X

x

x

x

x

7 + 1 = 8

X

x

x

x

X

x

x

X

x

x

X

x

x

X

x

X

x

X

x

X

x

x

x

x

x

x

x

x

x

x

x

x

15 + 1 = 16

Ici, on tombe sur les puissances de deux.