Introduction

Le problème du "voyageur de commerce" a intéressé les mathématiciens dès le 19ème siècle.

Sa complexité n'a pas facilité son étude et si l'on analyse tous les parcours possibles, pour n villes, le nombre de possibilités est  de (n-1)!. Pour 6 villes nous avons 120 possibilités, pour 10 villes plus de 362 000 et pour 60 villes plus de 10⁸⁰ soit le nombre d'atomes estimé dans l'univers.

Ceci peut expliquer pourquoi, le problème n'a pas été étudié sérieusement avant l'arrivée des ordinateurs dans les universités mais depuis 1954 de nombreux chercheurs l'ont traité.

Pour ma part, je me suis intéressé à ce sujet à l'automne 2004 et j'ai choisi de le proposer comme sujet pour le Rallye Sciences, concours ouvert dans l'académie de Grenoble pour des classes de troisième et de seconde.

Ce sujet, qui n'a d'ailleurs pas été retenu, peut être exploité sous forme de devoir à la maison pour des élèves de collège. Il introduit le calcul du nombre de possibilités et la propriété principale que j'utilise dans ma méthode de résolution. 

48 capitales des Etats-Unis