Exercice 2 — Longchemin

Sujet

Dans la ville de Longchemin, Kévin le plaisantin s'amuse à mettre des panneaux « obligation de tourner à droite » ou « obligation de tourner à gauche » ou enfin « obligation d'aller tout droit » à chaque intersection des rues de la ville, pour que les habitants parcourent la plus grande distance possible avant de revenir à leur point de départ. Les habitants de Longchemin, étant très respectueux du code de la route, suivent systématiquement les instructions des panneaux. Sur les schémas les panneaux seront indiqués par les symboles suivants :

• un \(\ll \mathrm{G} \gg\) pour tourner à gauche.
• un « D » pour tourner à droite.
• un < T> pour aller tout droit.

On notera bien qu'un panneau placé à une intersection est valable quelle que soit la rue d'où l'on vient, et que la direction à suivre s'obtient en se mettant à la place du conducteur. L'exemple suivant montre 3 trajets possibles d'un véhicule arrivant à une intersection « G », selon sa provenance :

Dans ce problème, nous allons aider Kévin à placer les panneaux à toutes les intersections de rues pour différents quartiers de formes rectangulaire de la ville de Longchemin. On appellera réseau le plan d'un tel quartier. Les intersections de rues seront aussi appelées carrefours. Un réseau est déterminé par ses dimensions, correspondant à la largeur et la longueur du rectangle, en nombre de rues.
Par exemple, les réseaux suivants sont respectivement de dimensions 1-1, 1-2, et 2-3.

Une configuration d'un réseau est la donnée des indications « G », « D », ou « T» pour chaque carrefour. Une fois un réseau configuré, on pourra identifier le chemin parcouru par une voiture entrant dans le quartier, et suivant scrupuleusement les indications de chaque carrefour. On supposera à chaque fois que le chemin commence par le carrefour situé dans le coin en bas à gauche. Voici des exemples de configurations pour les trois réseaux donnés plus haut :
a) Pour le cas \(n^{\circ} 1\), celui du réseau 1-1, une seule configuration est valide : il s'agit de celle donnée en exemple dans l'énoncé, et elle fournit un chemin de longueur 4.
Pour le cas \(\mathrm{nn}^{\circ} 2\), celui du réseau 1-2, on se convainc aisément qu'un chemin de longueur maximale fait le «tour du réseau». Ce chemin s'obtient avec une configuration où l'on place un panneau « \(\mathrm{G} \gg\) aux trois autres coins, et un panneau \(<\mathrm{T} \gg\) sur les deux panneaux restant. Le chemin résultant est de longueur 6.


b) - S'il s'agit de « D », on sort du réseau. La configuration n'est pas valide.

• S'il s'agit de « G », on se rend alors sur le bord supérieur du réseau. Si alors le panneau suivant est « T », la configuration n'est pas valide.
  S'il s'agit de \(\ll \mathrm{D}>\), la situation est la suivante :
  

Si l'on espère un jour revenir au carrefour initial, il faudra repasser par l'un des deux carrefours \(\ll \mathrm{G} \gg\) et \(<\mathrm{D} \gg\) par lesquels on vient de passer. Mais dans chaque cas, l'indication nous fera sortir du réseau : une telle configuration n'est pas valide.
Le panneau rencontré après le « G » ne peut donc être ni « T », ni « D » : c'est donc forcément un autre \(\ll \mathrm{G} \gg\).
Dès lors, on comprend bien que pour éviter de sortir avant le retour au carrefour initial, il faudra suivre le bord supérieur jusqu'au coin supérieur gauche. Un tel chemin sera de longueur maximal si la première «bifurcation» s'effectue au «bout» du réseau : ce chemin « fait le tour » du réseau :

Pour le réseau \(1-p\), un chemin maximal est donné par la configuration indiquée dans le schéma précédent, et il est de longueur \(2 p+2\) (soit le «périmètre» du réseau).

2. Longueur théorique du plus long chemin

a) Il est clair que le réseau \(n-p\) possède \((n+1)(p+1)\) carrefours (par exemple le réseau 1-2 a \(6=2 \times 3\) carrefours).
Le «périmètre» du réseau \(n-p\), en nombres de rue, est \(2 n+2 p\). Mais il y a bien sûr autant de rues que de carrefours sur un contour (de même qu'un polygone a autant de sommets que de côtés). Il y a donc \(2(n+p)\) carrefours sur le contour.
b) Un carrefour de coin ne connecte que deux rues, et il n'y a donc que deux façons de le traverser. D'autre part, puisqu'il faut nécessairement y « tourner », Un tel carrefour ne peut pas être noté «T», sinon la configuration ne serait pas valide. Mais s'il est noté «D» ou «G», seule l'une des deux façons évoquées ci-dessus pour le traverser est possible. Par exemple pour « D » au coin supérieur droit :