Énigme de la semaine 17

Au plus court.

(Extrait de Mathématiques sans frontières)

Le responsable du club de vélo de Centreville doit organiser un rallye cyclotouriste passant par les villages de Nordville, Sudville, Ouestville et Estville.
Le départ et l’arrivée de ce circuit doivent être à Centreville.
Le circuit doit passer au moins une fois sur chaque route marquée sur le schéma ci-contre qui précise les distances.
Il doit être le plus court possible.

Donner un itinéraire possible et calculer sa longueur totale.

Solution

Voici une solution possible :

La distance minimale est de 130 km.
On peut prouver qu’un tel parcours est minimal comme suit :
N, E, S et O sont chacun extrémités d’au moins trois tronçons du parcours, mais étant des points de passage, il sont nécessairement aux extrémités d’un nombre pair, donc de quatre tronçons au moins.
Le doublement des segments [NO] et [SE] - ou de [NE] et [SO] - permet alors d’économiser les segments parcourus deux fois, puisque la liaison double est commune à deux sommets du carré.