019 La grenouille
1 saut = directement de D ŕ A : une possibilité.
Procédons non sur le nombre de sauts, mais sur le nombre
de pavés.
zéro pavé : 1 possibilité D-A
1 pavé : 2 possibilités : D-A et D-1-A
2 pavés : 3 possibilités D-A, D-1-A, et D-2-A
Soit U(n) le nombre de possibilités avec n pavés.
Si on ajoute un pavé, toutes les combinaisons précédentes
sont bien entendu toujours possibles. S'y ajoutent les
trajets passant par le pavé n+1. Un trajet passant par
le pavé n+1 ne peut passer par le pavé n (rčgle des
pavés adjacents). En revanche, tous les trajets utilisant les n-1 premiers pavés sont permis. Ceux-ci
sont au nombre de U(n-1). Donc U(n+1)=U(n)+U(n-1), ce qui
me rappelle un certain Fibonacci.
n --> U(n)
0 --> 1
1 --> 2
2 --> 3
3 --> 5
4 --> 8
5 --> 13
...
Avec 20 pavés, notre grenouille peut choisir entre 10946
chemins.
|
|