Carrefour égyptien

Un petit sujet auquel je pense de temps à autres...

Soit un carrefour où \( n \) routes en sens unique s'intersectent. Supposons que le temps s'écoule de manière discrète, que les positions sur les routes soient discrètes aussi et numérotées à l'aide de \( \mathbb{Z} \), que le carrefour soit lui-même la position \( 0 \) commune à toutes les routes, qu'il ne puisse y avoir qu'un seul véhicule maximum en une position donnée à un instant \( t \) donné (sinon accident !), et que les véhicules avancent d'une position par unité de temps, dans le sens croissant des numéros.

C'est un carrefour sans feux tricolores. Pour éviter les collisions, le trafic routier doit être conçu et organisé. (on suppose les conducteurs de véhicules dénués de libre arbitre, à la limite c'est un système central qui prend le contrôle des véhicules et tout est automatisé). Une idée simple consiste à imposer à ce que chaque route ait un motif d'occupation par des véhicules périodique.

Par exemple, s'il y a \( n = 4 \) routes comme sur le dessin ci-dessus, une possibilité d'organisation est :

• sur la route 1 rouge, les véhicules doivent occuper les positions \( x_1 \) telles que \( x_1 - t = 0 (\mbox{mod } 4) \) ;
• sur la route 2 bleue, les véhicules doivent occuper les positions \( x_2 \) telles que \( x_2 - t = 1 (\mbox{mod } 4) \) ;
• sur la route 3 verte, les véhicules doivent occuper les positions \( x_3 \) telles que \( x_3 - t = 2 (\mbox{mod } 4) \) ;
• sur la route 4 violette, les véhicules doivent occuper les positions \( x_4 \) telles que \( x_4 - t = 3 (\mbox{mod } 4) \) ;

Cette organisation est optimale en ce sens qu'à chaque instant, le carrefour est occupé par un véhicule (imaginer un péage au carrefour ; 1$ à chaque passage de véhicule ; le péage maximise son rendement, 1$ par unité de temps, impossible de faire plus). Autre façon de le dire, le carrefour est saturé.

Une équation bilan de cette organisation est :

Nous adoptons le point de vue du péage et ne considérerons que des organisations optimales.

Une question que l'on peut se poser : est-il nécessaire que les fractions représentant chaque route soient égales ? La réponse est non. Par exemple, avec \( n = 3 \) routes, on peut chercher à implémenter l'égalité :

Il suffit alors de dire

• si \( t \) = 0, 1 ou 2 modulo 6, alors le véhicule situé au niveau du carrefour doit être un véhicule de la route 1 rouge ;
• si \( t \) = 3, ou 4 modulo 6, alors le véhicule situé au niveau du carrefour doit être un véhicule de la route 2 bleue ;
• si \( t \) = 5 modulo 6, alors le véhicule situé au niveau du carrefour doit être un véhicule de la route 3 verte ;

ce qui transposé en motifs donne

• sur la route 1 rouge, les véhicules doivent occuper les positions \( x_1 \) telles que \( (t - x_1) \mbox{ mod } 6 \in \{ 0, 1, 2\} \) ;
• sur la route 2 bleue, les véhicules doivent occuper les positions \( x_2 \) telles que \( (t - x_2) \mbox{ mod } 6 \in \{ 3, 4 \} \) ;
• sur la route 3 verte, les véhicules doivent occuper les positions \( x_3 \) telles que \( (t - x_3) \mbox{ mod } 6 \in \{ 5 \} \) ;

Combien existe-t-il d'implémentations distinctes de période 6 pour cet exemple ? On considère que deux implémentations ne différant que par leur phase sont identiques.

Que se passe-t-il si au lieu d'un carrefour, on en met plusieurs et qu'on veut tous les optimiser ?

A POURSUIVRE ...

LR, 12/08/2023.

PS : pourquoi "égyptien" ? Parce que référence aux fractions égyptiennes.

PPS : Animation sous Desmos