Article : Paths on a grid - Colegiul National C. Negruzzi (Iași - Roumanie)

Article
Résumé de la production
On imagine une triangulation cartésienne d'un rectangle qui représente les rues d'une ville et les points de la triangulation représentent les points d'intérêt touristique de la ville. La question est de compter le nombre des chemins possibles pour arriver d'un coin de la ville au coin diamétralement opposé, en prenant aussi en compte certaines contraines de circulation (certaines rues sont fermées) ou le passage par un point précis de la ville est imposé. On considère comme règle de déplacement du coin inférieur gauche vers le coin diamétralement opposé, qu'il faut avancer soit en montant soit en se déplaçant vers la droite. Pour résoudre cette question, plusieurs méthodes sont proposées : une comptant le nombre des chemins qui passent par chaque point de la triangulation, méthode qui est aussi programmée sur C++, ainsi qu'une méthode utilisant des arguments combinatoires. Le nombre maximal des rues qui peuvent être fermées de manière concomitante tout en gardant chaque point d'intérêt touristique accessible depuis le coin inférieur gauche est aussi calculé et programmé sur C++.

Une autre question est quelle est la probabilité pour deux personnes partant instantanément de deux coins opposés de la ville et marchant avec la même vitesse, de se croiser. On suppose que la personne partant du coin inférieur gauche se déplace seulement en prenant des rues montantes ou à droite et que la personne partant du coin supérieur droit se se déplace seulement en prenant des rues descendantes ou à gauche.
Mots clés
chemin
triangulation
principe d'inclusion-exclusion
probabilité