27.09.2018

Tonnerre de Braess !... Mésaventure sur la route des Olympiades

Drac et Ula, deux étudiants prêts à en découdre avec le premier examen des Olympiades internationales de mathématiques, s’apprêtent à résoudre une énigme supplémentaire imprévue. Découvre ici comment le paradoxe de Baer a joué les trouble-fêtes en Roumanie.

Bild: Ian Tormo

Radu était une personne extrêmement occupée depuis le début des festivités. Lui et son équipe travaillaient depuis plusieurs années à l’organisation des Olympiades internationales de mathématiques – une véritable fierté nationale pour le peuple roumain. Radu se vantait volontiers que tout était réglé à la minute.  Il a fallu, notamment, organiser le transfert des étudiants depuis leur hôtel vers le lieu où se déroulent les deux examens. Craignant que le trafic soit engorgé à ces heures matinales, Radu avait joué de ses relations gouvernementales, comme il est de tradition en Roumanie, pour obtenir de la mairie qu’elle ferme deux routes entre l’hôtel des participants et la salle d’examen au moment du transfert. Les soixante minibus affrétés pour l’occasion auraient donc la voie libre pour véhiculer les six-cents participants le jour J.

 

Mirela, qui gérait la compagnie de minibus depuis plusieurs années déjà, avait reçu les instructions de son vieil ami Radu pour le transport des étudiants. Radu avait particulièrement insisté sur la ponctualité. Ayant bien saisi toute l’importance que revêtent les Olympiades de mathématiques pour la nation roumaine, Mirela avait transmis des ordres clairs aux soixante chauffeurs engagés le jour de l’évènement. Chacun fut responsable de choisir parmi les deux itinéraires libérés par la mairie celui qu’il jugeât propice à transporter le plus rapidement possible les dix étudiants à sa charge. « Tout en respectant la signalisation », avait clairement insisté Mirela, ne connaissant que trop bien le style de conduite local.

 

*

De tous les chauffeurs mobilisés par Mirela, Alexandru est le plus expérimenté. En cette soirée du dimanche 8 juillet, la veille du premier examen des Olympiades, Alexandru, un verre de pálinka à la main, se pose tranquillement dans son fauteuil pour préparer son itinéraire du lendemain. Il a sur ses genoux une carte de la ville de Cluj-Napoca. Il a tracé les deux routes qui relient l’hôtel à la salle d’examen et a schématisé les itinéraires correspondants sur une feuille de papier.

Le premier itinéraire emprunte, tout d’abord, un dédale de ruelles étroites jusqu’à atteindre la Piata Unirii depuis laquelle on peut rejoindre la salle d’examen en traversant un tunnel sous la ville. Alexandru sait que la traversée du tunnel prendra précisément trente-et-une minutes. En revanche, bien que les ruelles ne représentent qu’une courte distance, la durée de leur traversée pour relier l’hôtel des participants à la Piata Unirii dépendra du nombre de minibus qui vont opter pour cet itinéraire. De par son expérience, Alexandru estime la durée en minutes de la traversée des ruelles par la moitié du nombre de minibus qui les emprunteront.

 

Le second itinéraire propose aux chauffeurs un tronçon d’autoroute pour relier le Grand Italia Hotel puis une courte route de campagne dont la dernière réfection remonte à l’époque communiste. Le tronçon d’autoroute, d’une longueur égale à celle du tunnel, durera également trente-et-une minutes, estime Alexandru. Quant à la route de campagne, tout comme pour le dédale de ruelles, Alexandru évalue à nouveau la durée du trajet par le nombre de minibus suivant cet itinéraire divisé par deux.

 

Soucieux de présenter au monde une image sans fausse note de la Roumanie, les soixante chauffeurs de Mirela se sont concertés pour offrir le transport le plus rapide aux étudiants. Il fut décidé que trente d’entre eux suivront le premier itinéraire par la Piata Unirii, alors que les trente autres passeront par le Grand Italia Palace. Cet arrangement représente un temps de trajet de quarante-six minutes par minibus selon les estimations d’Alexandru.

 

Alors qu’il s’apprête à ranger sa carte de la ville pour rejoindre son lit, le téléphone d’Alexandru se met à sonner. C’est un appel de Mirela. Un sentiment de surprise l’envahit ; que peut bien lui vouloir sa patronne à une heure aussi tardive alors que tout était déjà organisé pour le lendemain ? Il décroche.

 

  • Alexandru, s’exclame Mirela, il y a du nouveau pour demain.
  • Je t’écoute, répond Alexandru.
  • Radu de l’organisation des Olympiades m’a appelé. Pour désengorger le trafic de minibus demain, la mairie met également à disposition la Strada Piezisa qui relie la Piata Unirii au Grand Italia Palace. Vous avez désormais un troisième itinéraire à choix, explique Mirela.
  • Très bien.
  • N’oublie pas la consigne, précise encore Mirela, tu dois amener ton groupe d’étudiants le plus rapidement possible à la salle d’examen.

 

Alexandru voulu saluer Mirela, mais elle avait déjà raccroché. Probablement doit-elle encore informer les autres chauffeurs ce soir, se dit-il. Il se penche à nouveau sur sa carte de la ville. Il connait bien la Strada Piezisa. C’est une rue à sens unique, populaire auprès des étudiants en quête d’animation nocturne. En matinée, elle est d’ordinaire complètement désertée si bien que le cortège de minibus, peu importe sa taille, mettra moins d’une demi-minute pour la traverser le lendemain.

 

Alexandru attrape un stylo et se met à griffonner quelques chiffres. S’il emprunte les ruelles jusqu’à la Piata Unirii, puis la Strada Piezisa pour relier le Grand Italia Hotel et enfin la route de campagne, alors son temps de trajet ne dépassera pas trente-et-une minutes. Il économisera ainsi un quart d’heure par rapport à l’itinéraire initial. Se souvenant de la consigne qu’on lui a donnée de minimiser son temps de trajet personnel, Alexandru opte, sans hésitation, pour le nouvel itinéraire par la Strada Piezisa.

 

*

En éteignant sa lampe de chevet ce soir-là, Alexandru était content de pouvoir proposer ce voyage raccourci à son groupe d’étudiants le lendemain. Quelle bonne idée que d’avoir permis d’emprunter la Strada Piezisa, se répétait-il tout en s’endormant paisiblement. Bien au chaud dans son lit, Alexandru ne se doutait pas de la mésaventure qui l’attendait.

 

**

Lundi 9 juillet 2018. A la surprise générale, tous les minibus ont mis plus d’une heure pour transporter les étudiants. Radu est furieux. A la fin de l’examen, il exige des explications de Mirela. « Avant que l’on ne mette à disposition une rue supplémentaire, les minibus étaient censés effectuer le trajet de l’hôtel des participants à la salle d’examen en trois quarts d’heure, s’insurge Radu. Avec cet itinéraire supplémentaire il a fallu plus d’une heure, continue-t-il perplexe. » Mirela, qui essaie d’user de son charme pour calmer la situation, est elle-même confuse. Que s’était-il passé ? Comment l’ajout d’une option d’itinéraire supplémentaire pouvait-elle ralentir tout le monde ?

 

*

La solution vint de deux étudiants, Drac et Ula, qui avaient entendu les véhémences de Radu. Ils avaient tout de suite saisi le fin mot de l’histoire. Ils s’approchèrent de Mirela et Radu et suggérèrent l’explication suivante :

  • En proposant cette option supplémentaire aux chauffeurs, vous avez pensé que cela ne pouvait que contribuer à diminuer le temps de trajet des minibus, commença Drac.
  • Evidemment, coupa Radu.
  • Malheureusement, ce n’est pas si simple, répondit Ula.
  • Comment ça ? lança Mirela interloquée.
  • Les chauffeurs ont probablement fait leurs petits calculs hier lorsqu’ils ont été mis au courant pour l’ouverture de la Strada Piezisa. Ils sont arrivés à la conclusion qu’en empruntant cet itinéraire, ils économiseraient une quinzaine de minutes. Seulement, tout le monde a eu la même conclusion et lorsque tous sont passé par la Strada Piezisa ce matin, alors chacun a mis plus d’une heure pour relier la salle d’examen, expliqua fièrement Ula.
  • Mais ils avaient reçu la consigne de minimiser le temps de trajet, s’énerva Mirela. Ils vont avoir affaire à moi.
  • Encore une fois, ce n’est pas si simple, dit Ula. Drac, tu leur expliques ?
  • Ula a raison, intervint Drac. Certains parmi les chauffeurs se sont surement rendu compte que si tout le monde passait par la Strada Piezisa, alors cela prolongerait considérablement la durée du trajet. Cependant, un chauffeur seul n’a jamais avantage à revenir à l’un deux itinéraires initiaux, sachant que les autres passent par la Strada Piezisa. En effet, avec ce trafic, il mettrait alors précisément trente minutes jusqu’à la Piata Unirii, puis trente-et-une minutes pour traverser le tunnel jusqu’à la salle d’examen. Idem selon l’autre itinéraire. Soit, dans les deux cas, un total de soixante-et-une minutes, détailla Drac.
  • C’est-à-dire plus que les soixante minutes et des poussières que l’on met en passant par la Strada Piezisa. Faites le calcul ! ordonna Ula. Par peur d’enfreindre la consigne qui leur a été donnée, les chauffeurs ont donc tous jugé raisonnable d’emprunter la Strada Piesiza.
  • CQFD, conclurent Drac et Ula en chœur.

 

Mirela et Radu réalisèrent que les deux enfants avaient raison. Une telle situation aurait pu être évitée si les chauffeurs avaient eu le temps de se concerter et décidé de s’en tenir au plan initial en ignorant la Strada Piezisa. Toutefois, le fait d’avoir averti les chauffeurs la veille seulement ne leur laissait pas le temps nécessaire pour s’organiser. Mirela et Radu soupirèrent en concert. Jamais ils ne se seraient doutés qu’ajouter une route dans un réseau pouvait contribuer à ralentir le trafic global.

 

Par crainte de dépasser les bornes de l’insolence, Drac et Ula s’abstinrent de rajouter que ce paradoxe porte le nom du mathématicien allemand Dietrich Braess qui l’a découvert en 1968.

  • Celui qui connaissait ce paradoxe aurait pu prédire que tous les minibus emprunteraient certainement le même itinéraire, philosopha Drac lorsque Mirela et Radu furent éloignés.
  • Le fameux équilibre de Nash[1], continua Ula. Une situation dans laquelle aucun des acteurs n’a avantage à opter pour un itinéraire différent tant que les autres maintiennent leur choix.
  • Sans collaboration, il faut s’attendre à cette issue non optimale en termes de temps de trajet, conclut Drac.
  • Théorie des jeux élémentaire, lança Ula en cherchant la complicité de son ami.
  • Théorie des jeux élémentaire, acquiesça Drac en lâchant un sourire taquin.

 


[1] John Nash (1928-2015) était un mathématicien américain qui fut notamment lauréat du prix Nobel d’Économie en 1994 pour ses contributions en théorie des jeux. L’excellent film Un homme d’exception (A Beautiful Mind) (2001) retrace sa vie mouvementée par la schizophrénie dont il souffrait.

Autres articles

Informatique

Rapport d'un voyage: Les informaticiens aux CEOI en Pologne

Alors, qu'est-ce qu'on fait aux Olympiades de la science? Surmonter les barrières culturelles, manger des pizzas, lancer des frisbee, s'émerveiller des curiosités.... et passer un examen de temps en temps. Lisez ici ce que l'équipe suisse a vécu aux Olympiades d'Europe centrale d'informatique.

Faîtière

Philosophie

Biologie

Chimie

Géographie

Informatique

Mathématiques

Physique

Robotique

Des vacances qui te font autant de bien qu'à ton portemonnaie

Enfin elles sont là, les vacances d'été. Tu aimerais bien vivre quelque chose de spécial, mais n'as pas beaucoup de moyens à disposition. Pas grave : grâce à nos cinq idées, tu vas pouvoir épargner ton cochon-tirelire. Notre préférée : l'idée 5, « La chance ».

Faîtière

Philosophie

Biologie

Chimie

Géographie

Informatique

Mathématiques

Physique

Robotique

Checklist pour ton premier voyage – sans parent

L’été rime avec voyages. Est-ce que c’est la première fois que tu pars sans tes parents? Pour que tu n’oublies rien à la maison, nous avons concocté cette checklist pour toi. Succès garanti pour couler des vacances sans accroc.

Faîtière

Géographie

Informatique

Mathématiques

Physique

Robotique

Philosophie

Biologie

Chimie

Faisons un petit tour du monde

Au revoir la Suisse. Bonjour le Monténégro, l'Iran et le Japon: nos délégations préparent gentiment leurs valises et se rendront bientôt aux compétitions internationales. Tu ne fais partie d'aucune délégation? Ce n'est pas grave. Tu les accompagnes virtuellement – avec cette carte et la musique qui y convient dans les oreilles.

Chimie

Faîtière

Als die Selektion noch per Fingerzeig funktionierte

Die Schweizer Chemie-Olympiade feiert ihren 30. Geburtstag. Maurice Cosandey freut das besonders, denn die Olympiade ist sein Kind. Eine kleine...