
- Avancé
- Dénombrement et combinatoire
- Algorithmique et procédures
- Combinatoire et jeux
Énoncé
On dispose d’un échiquier rectangulaire comportant trois lignes et colonnes, où désigne un entier strictement positif. Une tour est placée sur la case inférieure gauche et doit rejoindre la case supérieure gauche.
La tour peut passer d’une case à une case contiguë par un côté commun, mais elle ne peut pas repasser par une case qu’elle a déjà occupée : sa trajectoire est dite auto-évitante. On note le nombre de chemins possibles sur un tel échiquier.
Q1Question 1 sur 3À faire
Déterminez $R(n)$ pour $n=1$, $n=2$ et $n=3$.
Indice offert
Sur chaque échiquier, numérote les lignes de bas en haut et les colonnes de gauche à droite. Repère alors la case de départ et la case d’arrivée, puis rappelle-toi qu’un déplacement ne relie que deux cases ayant un côté commun.
Q2Question 2 sur 3À faire
Déterminez $R(4)$ et $R(5)$.
Indice offert
Ici, $R(4)$ désigne le nombre de chemins auto-évitants sur l’échiquier de trois lignes et quatre colonnes. Repère la case de départ, la case d’arrivée et les déplacements autorisés, puis commence à tracer les chemins sans revisiter de case.
Q3Question 3 sur 3À faire
Proposez une méthode permettant de déterminer, par exemple, $R(2020)$.
Indice offert
Choisis une séparation verticale située avant la colonne la plus à droite atteinte par un chemin. Les deux extrémités du chemin étant à gauche de cette séparation, examine la parité du nombre d’arêtes horizontales qui la franchissent, puis utilise le fait qu’il n’existe que trois positions de franchissement.