Les coureurs

Publié le 29/01/17

En {n} points distincts d’une piste circulaire, {n} coureurs sont prêts à partir.
Au top départ, chacun démarre en choisissant aléatoirement un sens de rotation.
Quand deux coureurs se rencontrent, ils font demi-tour et repartent immédiatement.
Tous les coureurs vont à la même vitesse, et cette vitesse reste constante.
Montrer qu’au bout d’un certain temps, tous se retrouvent à leur point de départ.

Admettons que la vitesse de chaque coureur soit telle que, s’il n’avait pas à faire demi-tour, il parcourerait la piste en une heure. On va montrer que tous les coureurs se retrouvent à leur point de départ au bout de n heures.

Pour cela il convient d’imaginer une course « bis » (plus réaliste!) où les coureurs se croisent sans changer de direction (chacun continuant donc sur sa lancée). Il est clair que dans cette course « bis », tous les coureurs reviennent à leur position initiale (et dans leur direction initiale) au bout d’une heure.

À l’instant t, l’ensemble formé par les positions des coureurs est le même dans les deux courses. Au bout d’une heure (dans la course de l’énoncé), on retrouve donc l’ensemble formé par les positions initiales, chaque coureur se trouvant à la même position (et avec le même sens de déplacement) que l’un des autres coureurs au départ.

D’autre part, pendant toute la course de l’énoncé, les positions respectives des coureurs (quand on parcourt la piste dans le sens trigonométrique, par exemple) restent les mêmes.

Ainsi, et si au départ les positions (à partir d’une origine déterminée, et dans le sens trigonométrique) sont modélisées par la liste {(0,1,\ldots,n-1)}, les positions au bout d’une heure (même origine sur le cercle et même sens de lecture) sont modélisées par la liste {(p,p+1,\ldots,n-1,0,1,\ldots,p-1)} pour un certain entier {p}.

Au bout de deux heures, et par symétrie du problème, les positions des coureurs seront modélisées par {(2p,2p+1,\ldots,n-1,0,1,\ldots,2p-1)} (positions lues modulo {n}).

On voit qu’au bout de {n} heures, chaque coureur aura retrouvé sa position initiale, qui plus est avec la même direction de déplacement.

Remarque: il est possible que la configuration initiale se reproduise en moins de {n} heures. Par exemple, si tous les coureurs partent dans la même direction, ils ne croisent jamais et retrouvent leur position initiale, avec la même direction de déplacement, au bout d’une heure.