Nora prépare une réception sur un plan entièrement créé. Huit pièces portent les noms A, B, C, D, E, F, G et H. Elle veut choisir dans laquelle placer un repère que chaque pièce peut rejoindre. Camille reçoit deux demandes différentes : rendre le trajet le plus long aussi petit que possible, ou rendre aussi petite que possible la somme des huit trajets séparés. Nora ne les résume pas toutes deux par « mettre le repère au centre ». Le mot ne donnerait pas encore le critère qui choisira la pièce.
Artemide présente des lampes.
Nemo Lighting présente des lampes.
iGuzzini présente des luminaires.
Ces catégories seules ont été lues. Aucun éclairage, objet ou plan réel n'est adapté ; les pièces, liaisons, distances et demandes sont stipulées pour la feuille.
Les liaisons autorisées sont A–B, B–C, C–D, D–E, C–F, F–G et G–H. Chacune se parcourt dans les deux sens et vaut une unité abstraite. Le dessin est un arbre : tous les noms sont reliés, sans circuit. Chaque paire de pièces possède donc un chemin unique. La distance compte les traits de ce chemin, pas une durée ou une longueur mesurée dans un bâtiment. Le repère doit appartenir à l'une des huit pièces, et non au milieu d'un trait. Les trajets de la deuxième demande sont séparés ; leur somme n'est pas le coût d'une seule tournée passant partout.
Deux pièces bornent le plus long trajet à trois
Camille essaie C. Les distances depuis A, B, C, D, E, F, G et H valent deux, un, zéro, un, deux, un, deux et trois. Aucun trajet ne dépasse trois ; H atteint ce maximum. Avec F comme repère, les distances valent trois, deux, un, deux, trois, zéro, un et deux. Le maximum reste trois, atteint cette fois par A et E. Nora peut donc choisir C ou F pour une demande où tout le monde doit rejoindre le repère en au plus trois traits. Les listes différentes expliquent qui se trouve le plus loin dans chacun des deux choix.
Pour refuser une promesse de deux traits seulement, Camille prend A et H. Leur chemin A, B, C, F, G, H possède cinq traits. Si une pièce V se trouvait à distance au plus deux de chacun, le passage A vers V puis V vers H offrirait une marche de longueur au plus quatre. Le chemin unique entre A et H ne peut être plus long que cette marche, puisque ses détours éventuels peuvent être supprimés. Cinq ne peut donc respecter cette borne quatre. Tout repère laisse au moins l'une de ces deux pièces à trois ou davantage. Les deux propositions C et F atteignent la borne nécessaire, ce qui certifie le minimum trois.
Nora contrôle aussi que ce ne sont pas seulement deux exemples parmi des minima inconnus. A, E et H possèdent chacun un trajet maximal de cinq. B, D et G en possèdent un de quatre. Aucune de ces six pièces ne peut remplacer C ou F sous la limite trois. Camille conserve donc exactement les deux choix de la première demande. Elle peut départager leurs noms par une préférence supplémentaire, mais ne peut annoncer que G est aussi central parce qu'il occupe le milieu de la branche F, G, H visible sur le dessin.
Retirer les extrémités ensemble permet de retrouver ces choix
Camille veut refaire le choix sans calculer toutes les distances. Elle copie le dessin pour un calcul où les suppressions ne retirent aucune pièce de la demande originale. À la première étape, les pièces possédant une seule voisine sont A, E et H. Elle les enlève ensemble de cette copie. Restent B, C, D, F et G, avec leurs liaisons encore internes. À la deuxième étape, les extrémités sont maintenant B, D et G ; elle les enlève ensemble. Les deux noms qui restent sont C et F, les candidats déjà retenus. Leur distance maximale sera toujours annoncée sur les huit pièces d'origine, pas sur cette dernière copie réduite.
Cette suppression par couches conserve les candidats minimisant le trajet maximal. Sur un arbre ayant au moins trois pièces, une extrémité ne peut être un meilleur repère que sa seule voisine : pour toute autre pièce, le trajet depuis l'extrémité passe par cette voisine puis ajoute un trait. Le trajet le plus long depuis l'extrémité gagne donc un trait par rapport à celui de la voisine. Camille peut retirer les extrémités des candidats. Pour chaque pièce conservée, un trajet le plus long finit lui-même à une extrémité : s'il finissait ailleurs, on pourrait le prolonger sans former un circuit. Après suppression de toutes les extrémités, ces maxima diminuent chacun d'un trait ; leur comparaison entre pièces conservées reste donc la même.
Nora refuse en revanche une copie où Camille enlèverait une extrémité dès qu'elle la reconnaît, puis recommencerait immédiatement sans attendre la couche entière. En retirant dans l'ordre A, B, E, D, C et F, chaque nom est bien une extrémité au moment de son retrait. La copie finit pourtant sur G et H. Leurs maxima sur l'arbre original sont quatre et cinq, pas trois. Cette procédure a rongé certaines branches avant de traiter H, qui était une extrémité dès le départ. Nora impose donc les suppressions simultanées par couche. Retirer seulement des noms de degré un ne suffisait pas à conserver l'équilibre entre les branches que le calcul devait comparer.
La somme préfère C malgré le même maximum
Nora passe à sa deuxième demande, sur les huit pièces originales. Pour C, la somme des huit distances vaut douze. Pour F, elle vaut quatorze. Chacun avait un maximum trois, mais C rapproche davantage les trajets pris ensemble. Camille choisit donc C pour la somme, sans prétendre avoir amélioré la première borne. Le choix de F restait conforme à la première commande ; il est écarté de la seconde par une comparaison qui additionne tous les trajets. Nora place douze auprès de C et trois dans une autre colonne pour éviter que les deux nombres désignent la même opération.
La liste des sommes vaut vingt-deux en A, seize en B, douze en C, seize en D, vingt-deux en E, quatorze en F, dix-huit en G et vingt-quatre en H. Camille peut contrôler le minimum en examinant cette liste finie, mais elle veut aussi expliquer pourquoi déplacer un repère sur un trait change la somme. Elle retire provisoirement C–F du calcul et voit deux groupes : A, B, C, D, E d'un côté, F, G, H de l'autre. Rien n'a changé dans les chemins remis ; cette séparation sert seulement à compter les effets d'un déplacement.
En passant de F à C, Camille se rapproche d'un trait des cinq pièces du premier groupe et s'éloigne d'un trait des trois autres. La somme diminue de cinq et augmente de trois, soit deux de moins. Quatorze devient bien douze. Le trajet depuis F lui-même était zéro et devient un ; celui depuis C était un et devient zéro. Ils participent au compte de leurs groupes comme les autres noms, sans recevoir une exemption parce qu'ils peuvent porter le repère. Camille remet le déplacement F vers C avec ces deux groupes, plutôt qu'une intuition selon laquelle une pièce ayant trois sorties serait nécessairement le meilleur lieu.
Ce contrôle vaut pour toute liaison de l'arbre. Si le repère quitte U pour sa voisine V, les pièces situées du côté de V voient leur trajet raccourcir d'un trait, les autres l'allonger d'un trait. Avec n pièces et m du côté de V, la somme nouvelle moins l'ancienne vaut n moins deux m : n moins m trajets deviennent plus longs, m plus courts. Déplacer vers un groupe contenant plus de la moitié des pièces diminue donc la somme. Déplacer vers moins de la moitié l'augmente ; vers exactement la moitié la conserve. La comparaison porte sur le groupe situé au-delà du trait, pas sur le nombre de voisines directement attachées à V.
Une moitié dans chaque branche certifie un minimum global
Quand Camille retire C du dessin de comptage, les branches restantes contiennent A, B d'une part, D, E d'autre part, puis F, G, H. Leurs tailles sont deux, deux et trois, toutes inférieures à quatre, la moitié de huit. Aucun premier pas depuis C ne réduit donc la somme. Pour savoir si un lieu plus éloigné pourrait pourtant la réduire, Camille suit un chemin partant de C : le groupe situé au-delà de chaque trait suivant est contenu dans la première branche choisie. Il possède donc lui aussi moins de quatre pièces. Chaque pas de ce chemin augmente la somme. Toute autre pièce s'atteint par l'un de ces chemins ; C est ainsi le minimum unique, et non seulement un minimum parmi ses trois voisines.
À l'inverse, une pièce ayant une branche de plus de quatre ne peut minimiser la somme. F possède du côté de C les cinq noms A, B, C, D, E. Son premier pas vers C diminue le coût de deux. G possède du côté de F six noms et son pas vers F le diminue de quatre. H possède du côté de G les sept autres et son pas le diminue de six. Camille garde la condition de moitié avec sa preuve globale, plutôt que d'expliquer le minimum par le seul nombre de traits du chemin A–H. Ce chemin avait donné une borne pour le maximum ; ses deux pièces centrales n'avaient pas la même somme.
On appelle ici C une médiane de l'arbre pour la somme des distances. Ce n'est pas la médiane d'une liste de huit valeurs de trajet, obtenue en triant ces valeurs. Dans la première opération, Camille choisit une pièce puis additionne les huit distances qu'elle provoque. Dans la seconde, elle résumerait seulement une liste déjà calculée. Nora conserve donc la définition à côté du nom de C ; elle ne lui attribue pas une neuvième place inventée en prenant la moyenne de deux noms de pièces. Son repère reste l'un des sommets autorisés.
Les demandes concentrées en H déplacent la remise
Pour une autre feuille, H demande dix visites séparées au repère, chacune comptée une fois. Les sept autres pièces en demandent une chacune. Les poids sont stipulés, sans fréquentation réellement mesurée. Nora veut maintenant minimiser la somme de ces dix-sept trajets. Le dessin et ses distances ne changent pas. Camille ne conserve donc pas automatiquement C au motif que H n'est toujours qu'une pièce : dans cette commande, le nombre de trajets issus de H est une donnée différente du nombre de noms sur le dessin.
En C, la somme initiale douze reçoit neuf trajets supplémentaires depuis H, chacun de longueur trois : le total devient trente-neuf. En F, quatorze reçoit neuf fois deux, soit trente-deux. En H, les dix trajets de H sont tous nuls ; la somme vers les sept autres vaut vingt-quatre, comme sur l'ancienne feuille. Nora peut donc préférer H à C et F sous cette somme pondérée. Ce choix laisse toutefois les pièces A et E à distance cinq. Il ne satisfait pas la commande distincte qui exigeait au plus trois depuis tout le monde. Camille remet H avec vingt-quatre pour les dix-sept trajets, et non avec l'ancien maximum trois.
Le contrôle par groupes se pondère lui aussi. En quittant une pièce pour une voisine, Camille rapproche toutes les demandes du groupe d'arrivée d'un trait et éloigne les autres d'un trait. Elle compte dix-sept moins deux fois le poids total de ce groupe. En H, la seule branche contient les sept autres demandes, moins de la moitié de dix-sept. Tout pas qui s'éloigne de H traverse ensuite un groupe contenu dans cette branche, dont le poids ne peut augmenter. Les sommes augmentent donc le long de chaque chemin sortant de H. H est bien le minimum unique sous les poids, et non seulement la meilleure des trois candidates que Nora avait d'abord comparées.
Camille vérifie le chemin C, F, G, H. Les sommes pondérées valent trente-neuf, trente-deux, vingt-sept et vingt-quatre. Les diminutions sept, cinq puis trois viennent des poids douze, onze puis dix situés du côté de H au-delà des trois traits. Le poids majoritaire finit à H lui-même, où aucun groupe au-delà d'une sortie ne possède plus de la moitié. Nora ne remplace pas cette démarche par une préférence pour le dernier nom d'une branche. Si les poids revenaient tous à un, H retrouverait sa somme vingt-quatre et serait le pire choix de l'arbre original pour cette commande.
Quatre nouvelles extrémités laissent deux minima de somme
Une branche indépendante revient aux poids un partout, puis ajoute quatre nouvelles pièces W, X, Y et Z, chacune reliée à H par son propre trait d'une unité. Les huit anciens noms et traits restent présents. Le nouveau dessin est encore un arbre et compte douze pièces. Camille ne confond pas cette modification avec les dix demandes concentrées en H : les quatre destinations nouvelles se trouvent à un trait de H, tandis que les demandes précédentes de H se terminaient toutes au même sommet.
En F, les anciens trajets totalisaient quatorze ; chacun des quatre nouveaux est de longueur trois, par G puis H. La somme vaut donc vingt-six. En G, dix-huit reçoit quatre fois deux et vaut également vingt-six. En C, douze reçoit quatre fois quatre et vaut vingt-huit. En H, vingt-quatre reçoit quatre fois un, soit vingt-huit. Camille conserve F et G comme deux candidates de même somme. Elle contrôle ensuite le trait F–G : les six pièces A, B, C, D, E, F se trouvent d'un côté ; G, H, W, X, Y, Z forment les six autres. Un déplacement entre F et G rapproche six trajets et en éloigne six, ce qui explique l'égalité sans la déduire du seul voisinage des deux noms.
Cette égalité n'est pas un plateau sur tout le dessin. En F, les autres groupes au-delà d'une sortie n'ont pas plus de six pièces ; du côté de C, il y en a cinq. En G, le côté de H en possède également cinq. Les déplacements vers C ou H augmentent donc la somme, de vingt-six à vingt-huit. Plus loin, les groupes d'arrivée restent contenus dans ces cinq pièces et les augmentations continuent. Camille a exactement deux minima, F et G, parmi les sommets autorisés. Si Nora veut un seul nom, il lui faut un départage ; la somme ne l'avait pas encore fourni.
Nora reprend aussi le trajet maximal sur ces douze pièces. Entre A et W, six traits sont nécessaires, donc aucune pièce ne peut avoir un maximum inférieur à trois. Depuis F, A et E sont à trois, W, X, Y et Z aussi à trois ; toutes les autres sont plus proches. F atteint donc la borne trois. G, en revanche, laisse A et E à quatre ; il n'a pas le même maximum. Nora choisit F si elle veut garder la somme vingt-six tout en minimisant le trajet le plus long. Le deuxième critère départage ici les deux minima du premier, sans que Camille efface G de la liste où vingt-six était déjà conforme.
Un raccourci ferme un circuit et retire le certificat de moitié
Une autre feuille repart des huit pièces et ajoute A–H, de longueur un. Le chemin A, B, C, F, G, H possède maintenant un retour direct vers A et forme un circuit. Camille conserve les huit noms et cherche toujours la plus petite somme des distances, en choisissant cette fois le plus court chemin lorsque plusieurs existent. Le contrôle de moitié avait été établi pour un arbre ; Nora demande de tester réellement ce qu'il ferait sur ce nouveau dessin, plutôt que de conserver son nom comme certificat universel.
Camille calcule douze en C, quatorze en B et F, seize en A, D et G, dix-huit en H et vingt-deux en E. C reste le minimum. Pourtant, retirer C de cette copie laisse les cinq noms B, A, H, G, F reliés entre eux, et D, E dans un autre groupe. Le premier contient plus de la moitié des huit pièces. Une application automatique de l'ancien test déclarerait donc C non minimal et prescrirait un déplacement vers cette grande branche. Nora refuse cette conclusion : la liaison A–H a relié dans la copie deux anciennes branches de C. Elles n'offrent plus une seule entrée pour le même groupe. Camille conserve C avec douze, puis joint les distances qui contredisent le diagnostic faux, au lieu de modifier le score pour faire réussir le test.
Elle examine effectivement le déplacement C vers B. Les trajets vers A, B et H raccourcissent chacun d'un trait ; ceux vers C, D, E, F et G s'allongent chacun d'un trait. Le changement vaut donc cinq moins trois, deux de plus, et douze devient quatorze. Le groupe de cinq obtenu après retrait de C ne décrivait pas cinq rapprochements depuis B : F et G y appartenaient, mais se trouvaient mieux atteints depuis C par l'autre sortie, vers F. En retirant seulement C–B, le nouveau dessin reste relié par C, F, G, H, A, B ; il n'existe plus les deux côtés disjoints qui justifiaient huit moins deux m. Nora retire ce certificat de sa remise avec circuit et garde la comparaison des sommes réellement calculées pour choisir C.
Deux repères réduisent la borne, mais pas à un seul trait
La dernière commande repart des huit pièces originales et permet deux repères dans deux pièces différentes. Chaque destination rejoint le plus proche des deux ; Nora minimise le plus long de ces trajets minimisés. Camille ne divise pas automatiquement trois par deux : une pièce doit rejoindre un repère entier dans une pièce autorisée. Elle choisit C et H. A rejoint C en deux, B en un, D en un, E en deux, F en un ; G rejoint H en un. C et H ont eux-mêmes un trajet nul. Le maximum vaut deux.
Pour écarter une promesse d'un seul trait avec deux repères, Nora considère A, E et H. Les distances entre ces trois noms valent quatre, cinq et cinq. Un même repère situé à un trait de deux d'entre eux donnerait entre cette paire une marche de longueur au plus deux, impossible pour ces trois distances. Un repère ne peut donc prendre en charge deux de ces noms sous la limite un. Il faudrait au moins trois repères pour les couvrir tous. Camille refuse la borne un avec deux repères, puis conserve C et H à deux : le témoin et l'obstruction attestent ensemble le meilleur maximum permis.
Camille remet aussi C et G comme autre paire de maximum deux. Le groupe A, B, C, D, E peut rejoindre C, et F, G, H rejoint l'un des deux avec au plus un trait dans cette seconde partie. Cette alternative permet à Nora de choisir G plutôt que H pour le second nom, mais elle ne fait pas baisser deux. Camille garde la paire C, H dans la réalisation choisie et inscrit C, G dans les alternatives. Leur union C, G, H fournirait trois repères, ce qui n'est plus la commande de deux. Les listes alternatives ne peuvent être réunies en prétendant que le même dispositif comporte encore deux emplacements.
Le dossier final conserve C ou F pour le maximum original trois, C seul pour la somme originale douze, H pour la somme pondérée vingt-quatre, puis F sous les deux critères du dessin à douze pièces. La paire C, H répond à la dernière permission de deux repères sur huit pièces. Nora joint chaque liste de traits, de poids et de destinations au choix correspondant. Le même nom de pièce peut convenir à une commande et manquer une autre ; les comptes et les chemins remis donnent la raison précise de chacune de ces décisions.