Nora doit remettre une feuille issue d'une maison imaginaire à la dernière personne d'une chaîne. Sa première préparation porte un seul nombre à côté de chaque trajet. Camille lui demande ce que ce nombre mesure : des points dépensés pour ouvrir des passages, ou des unités avant l'arrivée ? Les deux ne sont pas interchangeables. Elles construiront une petite carte dirigée, avec des comptes entièrement stipulés, afin de choisir une remise qui réponde à une demande formulée avant le départ. Aucun quartier, transport ou temps réel ne se cache derrière les lettres.
Trois pages servent au seul décor de papeterie. Poppin présente des fournitures de bureau. Cavallini présente des articles de papeterie. Kikkerland présente une catégorie papeterie. Aucun chiffre, chemin ou délai de cette feuille ne vient de ces pages ; aucun de leurs objets n’est évalué.
Camille appelle R la page de départ et T la page de réception. Les trois pages intermédiaires sont A, B et C. Une flèche n'autorise qu'un sens. À chaque flèche, elle associe un couple : d'abord les points dépensés, ensuite les unités nécessaires. Les couples s'additionnent le long d'un trajet, sans partage de coût entre des essais différents. Elle interdit de répéter une page ; dans cette carte toutes les flèches avancent déjà vers T, de sorte qu'aucun cycle n'est possible. Le choix porte sur une seule remise, pas sur une distribution de plusieurs copies.
Sur la feuille, R vers A vaut (2,7), R vers B (5,3), R vers C (9,1). A rejoint directement T pour (0,2), B rejoint T pour (0,4) et C rejoint T pour (0,1). A peut aussi aller vers B pour (1,1) ou vers C pour (4,0). Enfin B peut aller vers C pour (1,0). Les zéros sont des coûts fictifs permis par cette feuille ; ils ne signifient pas qu'un déplacement réel serait instantané ou gratuit. Nora recopie les neuf flèches avant de classer les chemins, pour qu'une réponse ne puisse pas changer silencieusement la carte.
Elle commence par les trois remises directes à travers une seule page intermédiaire. R–A–T demande deux points et neuf unités. R–B–T demande cinq points et sept unités. R–C–T demande neuf points et deux unités. La colonne des points ordonne A, B, C ; celle des unités les ordonne C, B, A. Camille refuse donc de signer « le meilleur trajet est A » sur une fiche qui ne dit pas ce qu'il faut réduire. Cette première contradiction n'est pas une erreur d'addition ; elle expose la question que la fiche laissait vide.
Les flèches entre pages intermédiaires complètent la liste. R–A–B–T vaut trois points et douze unités. R–A–C–T vaut six points et huit unités. R–B–C–T vaut six points et quatre unités. R–A–B–C–T vaut quatre points et neuf unités. Il n'existe pas un huitième trajet simple sur les flèches données : après C, seul T suit ; après B, on choisit T ou C ; après A, on choisit T, B ou C. Camille inscrit les sept couples avec leur chemin, au lieu de garder seulement les quatre qui lui paraissent intéressants.
Retirer une ligne sans effacer la raison
Nora définit une comparaison précise. Un chemin domine un autre s'il ne demande pas davantage de points ni davantage d'unités, et améliore strictement au moins l'une des deux mesures. R–A–T, (2,9), domine R–A–B–T, (3,12) : il dépense moins et arrive plus tôt. Il domine aussi R–A–B–C–T, (4,9), avec les mêmes neuf unités. R–B–T, (5,7), domine R–A–C–T, (6,8). Ces trois retraits sont sûrs pour toute demande qui préfère simultanément moins de points et moins d'unités.
Mais la comparaison ne retire pas R–B–T devant R–A–T. B coûte trois points de plus et prend deux unités de moins. Elle ne retire pas non plus R–B–C–T, (6,4), devant R–B–T : ce détour ajoute un point et retire trois unités. R–C–T, (9,2), conserve deux unités, le meilleur temps de la liste, tout en coûtant davantage. Camille remet donc quatre chemins non dominés : (2,9), (5,7), (6,4) et (9,2). Le mot « non dominé » ne désigne pas quatre vainqueurs égaux ; il dit qu'aucun des quatre ne peut être barré sans connaître la demande.
Un visiteur propose de ne regarder que les deux extrêmes, le moins cher A et le plus rapide C. Camille lui oppose une permission concrète : la remise doit arriver en sept unités au plus et, parmi les chemins recevables, employer le moins de points. A manque la limite avec neuf. B l'atteint exactement avec sept et cinq points. Le détour B–C arrive en quatre mais en demande six ; C arrive en deux et en demande neuf. Le chemin B, que les deux extrêmes auraient caché, devient la réponse effective de cette commande. Nora inscrit « sept au plus » à côté de B, pas « rapide en général ».
Elle resserre ensuite la même demande à quatre unités au plus. B, sept unités, sort de l'ensemble permis ; A également. R–B–C–T arrive en quatre pour six points, tandis que R–C–T arrive en deux pour neuf. Le nouveau choix est donc B–C. Camille ne remplace pas les cinq points de la première commande par six dans une ligne qui garderait encore B–T : il s'agit d'un autre trajet, utilisant la flèche B–C. Cette modification remplie montre pourquoi les quatre lignes non dominées restent disponibles tant que la limite n'est pas donnée.
La contrainte inverse conduit encore ailleurs. Si la fiche autorise cinq points au plus et demande le délai le plus court, R–B–T fournit sept unités. R–A–T ne coûte que deux mais prend neuf. R–B–C–T prend quatre mais coûte six et ne peut être inscrit sous le plafond cinq. Nora refuse de traiter « au plus cinq » comme une préférence douce : une ligne hors permission n'est pas une candidate que l'on compense par son bon délai. Camille remplit le choix B et conserve la limite dans la remise, afin que personne ne lui attribue après coup les quatre unités du détour.
Un autre visiteur veut réduire une seule note obtenue en multipliant les points par un poids et les unités par le poids complémentaire. Nora écrit la note de A sous la forme 9−7λ ; celle de B, 7−2λ ; celle du détour B–C, 4+2λ ; celle de C, 2+7λ, avec λ entre zéro et un. Les flèches barrées plus haut ne peuvent gagner cette note, puisque les deux poids sont non négatifs. Camille peut ainsi vérifier le choix pondéré sans réénumérer un autre graphe. Elle rappelle que λ serait un choix créé pour la fiche, pas une mesure tirée d'une livraison.
B semble être un compromis naturel, mais cette note ne le choisit jamais. Pour qu'il batte A, l'inégalité 7−2λ ≤ 9−7λ demande λ ≤ 2/5. Pour qu'il batte le détour B–C, 7−2λ ≤ 4+2λ demande λ ≥ 3/4. Aucun λ ne vérifie simultanément ces deux conditions. Nora garde ce calcul avec le trajet B non dominé : « non dominé » n'implique pas « choisi par une somme pondérée ». Supprimer B au seul motif que la note ne l'élit jamais détruirait la réponse au plafond de sept unités.
Camille teste le milieu λ=1/2 pour comprendre le calcul plutôt que d'en faire une formule magique. A reçoit 11/2, B reçoit 6, B–C reçoit 5 et C reçoit 11/2. Le détour gagne cette note avec cinq, alors que la demande de sept unités au plus et du plus petit coût choisissait B pour cinq points. Les nombres cinq de ces deux phrases ne mesurent même pas la même chose : la note pondérée du détour d'un côté, les points réellement imputés à B de l'autre. La fiche conserve l'unité de chaque résultat pour empêcher cette coïncidence de devenir un faux accord.
Les étiquettes intermédiaires ne sont pas la réponse finale
Nora essaie maintenant de calculer chemin par chemin sans conserver toutes les histoires. À l'arrivée en B, elle rencontre directement depuis R l'étiquette (5,3). Elle rencontre aussi R–A–B avec l'étiquette (3,8). La seconde coûte deux points de moins mais demande cinq unités de plus. Aucune ne domine l'autre à B. Camille doit garder les deux si elle ne connaît pas encore la permission finale ; annoncer que « la moins chère » remplace l'autre à B ferait perdre R–B–T, réponse de la limite sept.
Prolongeons les deux étiquettes par B–T, qui ajoute (0,4). Elles deviennent (5,7) et (3,12). La seconde est alors dominée à T par R–A–T, (2,9), qui ne passait pas par B. Ce retrait final n'autorise pas à effacer d'avance l'étiquette (3,8) à B au prétexte qu'un autre chemin la dominera plus tard. Le test local et le test à l'arrivée utilisent les mêmes deux colonnes, mais pas le même ensemble de chemins disponibles. Nora montre exactement à quel stade sa liste de quatre réponses a été obtenue.
La sûreté d'un vrai retrait local a une justification plus modeste. Si deux chemins atteignent la même page, que le premier ne coûte ni ne dure plus que le second, et si tous deux peuvent recevoir la même suite de flèches, ajouter les mêmes nombres préserve les deux inégalités. Le second ne devient pas soudain meilleur sur cette suite commune. Cette preuve suppose les deux mesures additives et une même continuation autorisée. Elle ne dit pas qu'une étiquette moins chère mais plus lente peut être jetée ; les deux arrivées en B viennent précisément de montrer le contraire.
Camille ajoute sur une feuille d'essai une arrivée fictive supplémentaire en B avec l'étiquette (6,5), sans modifier le graphe remis. R–B atteint déjà B pour (5,3), strictement meilleur dans les deux colonnes ; toute suite commune rendrait (6,5) inutile. Elle raye cette étiquette d'essai et garde (3,8), qui n'a pas la même relation. La distinction est opératoire : rayer (6,5) économise une ligne sans changer une décision, tandis que rayer (3,8) demanderait une information que la comparaison ne contient pas. La feuille d'essai reste marquée comme ajout et ne devient pas une huitième route du graphe principal.
Une autre erreur naît d'une addition correcte au mauvais endroit. À A, (2,7) est l'arrivée depuis R. Ajouter A–T donne (2,9). Ajouter A–C donne (6,7) à C, puis C–T donne (6,8). On ne peut pas écrire (6,7) comme temps de remise à T : il manque la dernière unité. À C, l'arrivée directe (9,1) et l'arrivée via A (6,7) sont incomparables, puis deviennent (9,2) et (6,8) à T. Nora signale ce changement de page dans la marge ; les couples d'une page intermédiaire ne sont pas encore des reçus.
B–C fournit une seconde arrivée en C : R–B–C y vaut (6,3), et C–T la porte à (6,4). Elle domine alors l'arrivée en C via A, (6,7), avec les mêmes six points et quatre unités de moins. Cette fois l'effacement peut être fait avant T, car les deux étiquettes sont effectivement à C et possèdent la même flèche de sortie. Le chemin direct R–C reste (9,1), incomparable avec (6,3). Camille garde à C ces deux étiquettes utiles, puis les prolonge en deux reçus distincts, (6,4) et (9,2).
Nora peut maintenant expliquer pourquoi une recherche qui ne garde qu'un seul nombre par page ne répond pas à toutes les fiches. Si elle ne garde à C que le coût six, elle perd le temps deux de la voie directe. Si elle ne garde que le temps un, elle perd la voie à six points compatible avec la limite quatre. Même une liste correcte à C ne dispense pas de vérifier la destination : B a conservé deux étiquettes dont l'une devient finalement dominée. Camille livre une petite table par page et une table finale, sans promettre qu'un ordre de traitement particulier résoudrait tous les graphes réels.
Nora reçoit ensuite une règle d'une autre nature : au plus une page intermédiaire peut être visitée. La liste à quatre lignes non dominées ne suffit plus telle quelle, car R–B–C–T visite B et C. Parmi les chemins admis restent R–A–T, R–B–T et R–C–T. Si la limite de temps reste quatre, seul C arrive assez tôt ; Camille remet (9,2), et non (6,4). Le détour n'a pas été dominé sur ses deux nombres : une troisième condition l'a rendu irrecevable. Nora ajoute une colonne de pages visitées au lieu de falsifier le temps quatre de l'ancien chemin.
Si la même règle autorise deux pages intermédiaires, B–C revient parmi les candidats. Sous la limite quatre, Camille revient à six points et quatre unités. Les chemins R–A–B–T et R–A–C–T utilisent eux aussi deux pages, mais sont dominés par les routes déjà gardées ; R–A–B–C–T en utilise trois et reste exclu avant même la comparaison. Les deux décisions, neuf sous une page et six sous deux, sont rendues sur la même carte. Nora montre que « revenir » ici signifie rouvrir une permission de la commande, pas ressusciter une flèche fermée ni modifier un couple.
Cette troisième condition modifie la portée du retrait par dominance. Une route dominée dans les deux nombres peut parfois utiliser moins de pages que celle qui la domine ; l'effacer avant de vérifier la limite de pages serait alors injustifié. Dans notre liste, R–A–B–T est dominée par R–A–T, qui utilise aussi moins de pages, et peut toujours être retirée. R–A–C–T est dominée par R–B–T, qui utilise également moins de pages. Camille vérifie ces relations une par une avant de réutiliser sa table à quatre lignes. Elle ne déclare pas que toute table à deux colonnes resterait suffisante sous une troisième exigence inventée plus tard.
Une flèche fermée change les candidats, pas les nombres anciens
L'organisateur annonce enfin que B–T est fermée avant le départ. Nora n'efface pas la ligne historique qui avait fait gagner B sous sept unités ; elle la marque indisponible dans ce nouvel état. R–B–C–T reste permis et arrive en quatre pour six points. R–A–T reste à neuf pour deux, R–C–T à deux pour neuf. Sous la limite sept, B direct a disparu ; le détour B–C devient le moins cher des chemins recevables pour six points. La fiche de fermeture montre la différence entre un chemin moins bon et un chemin qui n'existe plus dans la commande courante.
Camille examine un retrait plus étroit : fermer seulement B–C. Sous sept unités, R–B–T demeure recevable pour cinq points et gagne encore. La fermeture de B–C ne transforme pas la voie B–T en sept unités nouvelles, pas plus qu'elle n'efface C direct. Les deux fermetures portent des noms voisins mais changent deux ensembles distincts. Nora inscrit pour chacune la liste des chemins encore autorisés avant de choisir ; elle ne recycle pas la réponse de la première fermeture sous le seul mot « B fermé ».
Si B–T et B–C sont toutes deux fermées, aucune remise par B ne rejoint T. À sept unités au plus, R–A–T prend neuf et manque la limite ; R–C–T prend deux pour neuf points et reste la seule des trois voies directes recevable. R–A–C–T prend huit et manque elle aussi la limite. Camille choisit donc C à neuf points et deux unités. Elle ne prétend pas que C était la meilleure réponse au début : sa sélection dépend des deux retraits réellement annoncés. La feuille conserve la suite des états plutôt que de présenter neuf comme le coût de l'ancien B.
Une annonce plus tardive ne peut être traitée de la même façon. Si Camille a déjà engagé R–B et apprend à B que B–T est fermé, elle peut encore suivre B–C–T : à partir de B cela ajoute (1,1), soit un total (6,4). Elle n'a pas le droit de repartir de R pour prendre A sans le dire, ni de présenter les cinq points de B–T comme dépensés après une flèche fermée. Nora écrit l'état « arrivée en B pour (5,3) » et la seule suite utilisée. Ce reçu dépend du moment de l'annonce ; il ne garantit rien si B–C ferme également avant la décision.
À l'inverse, si la fermeture de B–T était connue dès R, Camille pouvait choisir directement le chemin B–C–T sous sept unités. Les deux histoires se rejoignent au couple (6,4) mais ne donnent pas le même droit d'affirmer une préparation initiale. Dans l'une, elle a préparé le détour ; dans l'autre, elle a réparé après avoir atteint B. Le résultat arithmétique commun n'efface pas la différence entre plan et réalisation. Le récit de remise garde le moment auquel l'information est devenue disponible, sans faire de ce détail une observation du monde extérieur.
Nora rassemble ses décisions dans trois lignes : sans limite supplémentaire, deux points choisissent A ; sous sept unités, cinq points choisissent B ; sous quatre, six points choisissent B–C. La fermeture de B–T fait passer la ligne de sept unités à B–C ; la double fermeture B–T et B–C la fait passer à C pour neuf. Chaque ligne porte son état de flèches, sa limite et son couple complet. Camille remet ces lignes avec la feuille des sept trajets. Un lecteur peut vérifier chacune sans mêler un coût d'un état au temps d'un autre.
La maison fictive n'a livré ni tarif, ni heure d'arrivée, ni recommandation de papeterie. Elle a livré une méthode de lecture de sa propre feuille : garder les deux mesures, barrer seulement les chemins réellement dominés, demander la limite avant de choisir et noter quand une flèche cesse d'être disponible. Nora conserve le trajet B même si aucune somme pondérée ne l'élit, parce qu'une limite explicite l'a réellement rendu nécessaire. Camille signe le reçu correspondant à la commande choisie, non une promesse que la même route serait préférable quelle que soit la question.
Quand deux écarts doivent rester supportables ensemble
La destinataire change cette fois la forme de sa permission, sans changer une flèche. Elle veut éviter qu'un trajet soit très éloigné de l'idéal dans l'une ou l'autre colonne. Le meilleur score isolé est deux points, obtenu par A ; la meilleure durée isolée est deux unités, obtenue par C. Aucun chemin ne réalise le couple idéal (2,2). Camille donne donc deux tolérances propres à son exercice : trois points au-dessus du minimum de points, cinq unités au-dessus du minimum de durée. Pour chaque trajet, Nora divise son excès de points par trois et son excès de durée par cinq, puis conserve le plus grand des deux quotients. Ce maximum mesure la violation la plus forte des deux tolérances ; additionner les quotients répondrait à une autre demande.
Nora remplit la feuille avant de choisir. Pour R–A–T, les excès sont zéro et sept : le maximum vaut sept cinquièmes. Pour R–B–T, ils sont trois et cinq : les deux quotients valent un. Pour R–B–C–T, ils sont quatre et deux : le maximum vaut quatre tiers. Pour R–C–T, ils sont sept et zéro : le maximum vaut sept tiers. Le minimum unique de ces quatre maxima est donc un, atteint par B. La règle peut aussi se lire comme deux portes à franchir ensemble : ne pas dépasser cinq points et sept unités. Parmi les quatre trajets, seul B satisfait simultanément ces deux bornes, tandis que B–C manque la borne de points même s'il arrive plus tôt. Camille remet le chemin B avec le critère et les deux écarts, pas une moyenne des qualités.
Les trois autres chemins du catalogue n'ont pas été oubliés dans cette preuve. Chacun était dominé en points et en durée par un chemin conservé ; soustraire les mêmes minima, diviser par des tolérances positives puis prendre le maximum ne peut pas rendre un chemin dominé meilleur que son dominant. Nora peut donc achever la comparaison sur quatre lignes. Il serait faux de copier ici le refus de B sous la somme pondérée : aucune valeur du poids unique ne faisait gagner B dans cette autre règle, alors que la règle du pire écart normalisé le choisit effectivement. Les deux calculs emploient les mêmes flèches, mais l'un peut compenser une mauvaise colonne par l'autre et l'autre exige que les deux écarts restent supportables. Le reçu précise laquelle de ces deux permissions Camille a réellement donnée.