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.