H165. Solutions de mobilité dans un parc de loisirs Imprimer
H. Graphes et circuits

calculator_edit.png  

N attractions sont disséminées dans un vaste parc de loisirs. Le réseau de voies piétonnes qui les relie entre elles est conçu de  sorte que pour aller de n’importe quelle attraction n°i à une autre attraction n°j, ou bien il y a une voie directe désignée par (i,j) ou bien on passe par une attraction intermédiaire n° k en empruntant la voie (i,k) puis la voie (k,j).On se fixe également pour contrainte qu’il y a au maximum d voies qui partent de chaque attraction. Sur chaque voie on peut marcher dans les deux sens si bien que h165  i ≠ j, (i,j) ≡ (j,i).

Q₁ N = 8. Déterminer les valeurs de d qui rendent possible la construction d’un tel réseau et donner la représentation de ce réseau pour la plus petite valeur possible de d.

Q₂ Même question avec N = 16.

 Solution



Ce problème a été posé au printemps 1991 au Tournoi des Villes (niveau Senior A). La solution officielle (en anglais) a été établie par pdfAndy Liu (problèmiste bien connu et très prolixe) et donne les réponses d = 3 à Q1 et d=5 à Q2 selon l'hypothèse que les voies pour aller d'une attraction à une autre peuvent se croiser.Il démontre par la même occasion que ces deux valeurs de d sont les plus peites possibles.
pdfThérèse Eveilleau,pdfRémi Planche,pdfDaniel Collignon,pdfJean Nicot,pdfLouis Rogliano ont obtenu tout ou partie de ces résultats avec les mêmes hypothèses. pdfJean Louis Legrand a traité le problème en considérant que les voies ne se croisent pas.