On dispose d’un échiquier rectangulaire comportant trois lignes et n colonnes. Une tour est placée sur la case inférieure gauche et on l’amène sur la case supérieure gauche de la façon suivante : elle peut passer d’une case à une case contigüe (par un côté commun) mais ne peut pas repasser par une case qu’elle a déjà occupée auparavant (sa trajectoire est dite auto-évitante).
On note R(n) le nombre de chemins possibles sur un tel échiquier.
1) Déterminez R(n) pour n = 1, 2 et 3.
2) Déterminez R(4) et R(5).
3) Proposez une méthode pour déterminer par exemple R(2020).