Aller au contenu

Chemins auto-évitants

avril 2020
Ajouter aux favorisSignaler une erreur

Énoncé

On dispose d’un échiquier rectangulaire comportant trois lignes et n colonnes, où n 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 R(n) 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.

Problème suivant : Chez ce cher serge

Créez votre compte gratuit

Avec un compte, les indices sont gratuits. La vérification de vos réponses et l’aide de Tablo fonctionnent avec des crédits IA, inclus chaque mois dans l’abonnement.