Article : Alphaville - Collège Stéphane Mallarmé (Marseille)

Résumé de la production
Dans une ville où les rues forment un quadrillage, on souhaite placer des pharmacies aux carrefours de sorte que chaque carrefour soit à une distance 0 ou 1 d'une pharmacie. Comment réussir cela en plaçant le moins de pharmacies possibles ?
Les auteurs présentent une méthode systématique où les pharmacies sont disposées en losanges et font l'analogie avec le déplacement d'un cavalier aux échecs.

Mots clés
quadrillage
graphe
distance
minimum
stratégie optimale