Pour composer une page de son livre privé fictif, Lucie dessine des positions sur une ligne. Des unités y sont présentes ; elle veut les répartir autrement, en déplaçant chacune vers une place d’arrivée donnée. Elle ne cherche ni un centre où toutes se rencontreraient ni une vitesse de déménagement. Elle demande une affectation et la somme des distances parcourues. Martin lui remet d’abord une différence entre deux moyennes. Lucie veut vérifier ce que ce nombre borne, puis construire une répartition dont le coût est réellement minimal.
Les positions, les unités et les décisions sont stipulées pour le dessin. Les unités ont toutes la même masse un ; les places d’arrivée reçoivent chacune une unité. Aucun feuillet réel, lecteur ou parcours matériel n’est observé. La distance entre deux positions est leur différence absolue. Les raisonnements de transport sur une ligne sont classiques, sans invention revendiquée.
La notice 337247 du Met classe l’objet parmi les estampes.
La notice 337248 du Met classe l’objet parmi les dessins.
La notice 337249 du Met classe l’objet parmi les dessins.
Ces catégories ne fournissent aucun parcours ; positions, masses et coûts sont définis sur notre page, sans examen d’image.
Une affectation qui évite les allers et retours inutiles
La première feuille porte deux unités en zéro, une en deux et une en cinq. Les quatre places finales sont une en zéro et trois en cinq. Les unités peuvent rejoindre directement n’importe laquelle des places ; aucune liaison n’est limitée. Lucie veut la somme des quatre distances, et non la distance d’un seul point représentant le groupe. Une unité demeurant sur sa position occupe également sa place finale et contribue zéro au coût.
Martin prépare un relevé où l’unité partie de cinq rejoint zéro. Les deux unités parties de zéro rejoignent cinq, ainsi que celle partie de deux. Le coût vaut cinq plus cinq plus cinq plus trois, soit dix-huit. Les départs et les arrivées sont bien ceux de la demande. Lucie ne rejette donc pas cette feuille pour avoir perdu une unité. Elle examine les deux lignes cinq vers zéro et zéro vers cinq : leurs destinations peuvent être échangées sans toucher aux deux autres lignes. Elle laisse alors la première unité en cinq et l’autre en zéro. Dix de distance disparaissent de ces deux trajets, sans changer la répartition finale.
La nouvelle feuille laisse une unité en zéro et celle de cinq sur place ; l’autre unité de zéro rejoint cinq et celle de deux rejoint cinq. Le coût vaut zéro plus zéro plus cinq plus trois, soit huit. Lucie la retient comme proposition améliorée. La correction a porté sur les destinations attribuées, avant tout déplacement. Elle ne raconte pas deux transports accomplis qu’une soustraction aurait annulés après leur arrivée. Le dessin de dix-huit reste une affectation permise, mais la feuille de huit remplace ses deux lignes opposées pour la préparation choisie.
Lucie cherche maintenant une borne valable pour toutes les affectations, y compris celles qu’elle n’a pas dessinées. Elle coupe la ligne entre zéro et deux. Deux unités sont initialement à gauche de cette coupure, contre une place finale seulement. Au moins une unité doit donc franchir l’intervalle de longueur deux vers la droite. Elle coupe ensuite entre deux et cinq : trois unités sont initialement à gauche, contre une place finale. Au moins deux doivent franchir ce second intervalle, de longueur trois. Toute affectation paie ainsi au moins une fois deux et deux fois trois, soit huit. La proposition retenue atteint cette borne.
Le passage de zéro à cinq contribue aux deux intervalles : deux puis trois, soit ses cinq de distance. Le passage de deux à cinq ne contribue qu’au second, pour trois. Lucie peut donc ajouter les contributions des coupures sans compter un trajet fictif supplémentaire. Elle a décomposé la distance de chaque ligne de l’affectation en ses morceaux géométriques. Martin avait proposé trois comme coût, en additionnant seulement les nombres un et deux de passages obligés ; cela compterait les traversées sans leur longueur. Lucie conserve huit pour les positions zéro, deux et cinq, dont les intervalles n’ont pas la même taille.
Les comptes cumulés fixent les passages nets nécessaires
Lucie note les quantités cumulées depuis la gauche. Après zéro, le départ contient deux unités et l’arrivée une ; leur différence est un. Après deux, les quantités sont trois et une ; leur différence est deux. Après cinq, elles sont toutes deux quatre et la différence revient à zéro. Les deux différences intérieures déterminent les passages nets nécessaires : une unité sur le premier intervalle, deux sur le second. Le dernier zéro exprime l’égalité des masses totales, sans fournir à lui seul les distances à parcourir.
Pour une coupure donnée, le nombre de trajets vers la droite moins celui des trajets vers la gauche vaut cet écart cumulé. Leur somme est au moins la valeur absolue de leur différence. Chaque trajet qui traverse l’intervalle paie sa longueur. En multipliant la valeur absolue de l’écart par cette longueur, Lucie obtient donc une borne locale. Elle les additionne sur tous les intervalles entre positions successives : chaque trajet contribue à exactement les intervalles qu’il traverse. La borne concerne ainsi toutes les destinations possibles des unités, et pas seulement les deux lignes qu’elle a échangées dans son premier essai.
Dans l’essai à dix-huit, le premier intervalle reçoit deux passages vers la droite et un vers la gauche, soit trois au total pour un net de un. Le second reçoit trois vers la droite et un vers la gauche, soit quatre au total pour un net de deux. Son coût est trois fois deux plus quatre fois trois, encore dix-huit. Le relevé à huit atteint les mêmes passages nets avec seulement un puis deux passages totaux. Lucie localise les dix économisés : une paire de passages opposés était retirée sur chacun des deux intervalles, économisant deux fois deux puis deux fois trois. L’égalité des passages nets n’avait donc pas rendu les deux affectations équivalentes pour le coût.
Elle donne au destinataire de la page les masses finales et le relevé de huit, accompagnés des deux écarts cumulés. Les masses seules ne désignent pas les lignes du premier essai ; elles permettaient plusieurs préparations. Les écarts donnent en revanche une borne sur toutes ces préparations. Lucie ne joint pas le parcours de dix-huit sous le titre « distance imposée par les masses ». Elle garde ses lignes comme témoin d’un choix plus coûteux, afin que la différence entre nécessité de passage et passage effectivement préparé puisse se contrôler sur le même dessin.
Un déplacement moyen petit peut cacher deux directions nécessaires
Une deuxième feuille porte une unité en zéro, deux en deux et une en cinq. Elle demande deux unités finalement en zéro et deux en cinq. Le total de positions pondérées passe de neuf à dix. La moyenne passe donc de neuf quarts à cinq demis, avec une différence un quart. Multipliée par la masse totale quatre, cette différence fournit un déplacement signé total de un. Martin souhaiterait l’utiliser comme la distance minimale de la répartition ; Lucie examine d’abord les coupures.
Après zéro, il manque une unité à gauche : la quantité initiale vaut une, contre deux finales. L’écart cumulé est moins un, exigeant un passage de longueur deux vers la gauche. Après deux, l’écart est au contraire plus un : trois unités initiales à gauche, contre deux finales. Un passage de longueur trois vers la droite est également nécessaire. Leur coût commun est au moins deux plus trois, soit cinq. Les deux exigences ont des sens contraires, mais elles concernent des intervalles différents. Les soustraire pour conserver un seul coût net ferait disparaître une partie des distances que les unités doivent réellement parcourir.
Lucie atteint cinq en laissant les unités de zéro et de cinq sur place, puis en envoyant l’une des deux unités de deux vers zéro et l’autre vers cinq. La première parcourt deux vers la gauche, la seconde trois vers la droite. Leur déplacement signé total est moins deux plus trois, soit un ; leur distance totale est deux plus trois, soit cinq. Martin peut conserver le un comme contrôle du changement de somme des positions. Lucie retire uniquement son interprétation comme coût minimal atteint. Elle lui remet deux nombres répondant à deux calculs différents, sans changer les masses pour les faire coïncider.
La moyenne demeure une borne inférieure générale après multiplication par la masse totale : la valeur absolue de la somme des déplacements ne peut dépasser la somme de leurs valeurs absolues. Elle peut toutefois être strictement trop faible lorsque les sens nécessaires diffèrent. Sur la première feuille, tous les passages du relevé optimal allaient vers la droite ; le changement total de positions valait huit et retrouvait le coût. Sur la seconde, les écarts changent de signe et les deux moyens divergent. Lucie garde le contrôle cumulé pour sa décision, plutôt que supposer que la première égalité autorisait la même méthode sur toutes les répartitions.
Relier les positions dans leur ordre produit une réalisation minimale
Lucie veut disposer d’une construction pour une feuille plus grande, sans vérifier toutes les permutations de places. Elle écrit les positions de départ dans l’ordre croissant, en répétant une position autant de fois qu’elle possède d’unités. Elle fait de même avec les places finales. Puis elle relie la première occurrence de départ à la première d’arrivée, la deuxième à la deuxième, et ainsi de suite. Sur la seconde feuille, les suites sont zéro, deux, deux, cinq et zéro, zéro, cinq, cinq. Cette construction donne précisément les deux unités laissées sur place et les deux déplacements qui atteignent cinq.
Pourquoi cette construction atteint-elle les bornes de chaque coupure ? Si une ligne part d’un point situé à gauche de la coupure pour arriver à droite, une autre ligne passant dans l’autre sens aurait un départ plus grand mais une arrivée plus petite. Les rangs de départ et d’arrivée seraient alors inversés. Cela n’arrive pas quand les occurrences de même rang sont reliées. Sur chaque intervalle, tous les passages préparés vont donc dans le sens de l’écart cumulé, ou aucun passage n’existe si cet écart est nul. Leur nombre total égale sa valeur absolue. La construction atteint simultanément toutes les bornes locales, et donc leur somme.
Cette propriété ne demande pas que les différentes unités placées ensemble aient des identités interchangeables dans un document réel. Notre permission les traite ici comme unités équivalentes dont seule la position compte. Si une autre demande imposait une destination à une identité précise, la liste des affectations autorisées changerait et la construction par rang ne suffirait plus à la garantir. Lucie n’ajoute pas cette restriction à la feuille qu’elle a contrôlée. Pour deux occurrences de deux dans son second exemple, elle peut choisir laquelle part à gauche ; les masses et le coût restent identiques, sans conclusion sur des feuillets réels qui porteraient des contenus différents.
Elle peut également améliorer un relevé arbitraire par des échanges. Prenons deux départs a et b, avec a inférieur ou égal à b, et deux arrivées c et d, avec c inférieur ou égal à d. L’affectation croisée relie a à d et b à c. La remplacer par a vers c et b vers d ne peut augmenter la somme des distances absolues. L’économie vaut deux fois la longueur commune aux intervalles de a à b et de c à d ; elle est nulle si les intervalles ne se recouvrent pas. En retirant successivement les inversions de rang, Lucie obtient donc une affectation ordonnée de coût au plus égal, dont les coupures fournissent ensuite le certificat minimal.
Sur les deux lignes zéro vers cinq et cinq vers zéro du premier essai, les deux intervalles sont tous deux de zéro à cinq. Leur intersection a une longueur cinq ; l’échange économise dix. Lucie retrouve exactement sa première correction. Sur deux départs zéro et un et deux arrivées deux et trois, les intervalles des départs et des arrivées sont disjoints. Une affectation croisée ne coûte alors pas davantage en distance absolue. Cette seconde observation empêchera de transformer la construction minimale par rang en une prétention d’unicité. La possibilité de supprimer une inversion sans augmenter le coût ne dit pas que toute inversion augmentait déjà le coût.
Un coût minimal peut laisser plusieurs affectations à départager
La nouvelle feuille possède seulement les deux unités de zéro et un, avec les deux places deux et trois. L’affectation ordonnée donne zéro vers deux et un vers trois : deux plus deux, soit quatre. La croisée donne zéro vers trois et un vers deux : trois plus un, encore quatre. Les deux unités avancent dans chaque proposition ; la somme des déplacements est déterminée par les positions finales moins les initiales, cinq moins un. Lucie peut donc remettre chacune comme réalisation de la distance minimale, même si une seule est ordonnée par rang.
Le certificat par coupures donne un passage sur l’intervalle zéro–un, deux sur un–deux et un sur deux–trois. Chacun a une longueur un, d’où quatre. Les deux propositions atteignent les trois bornes ; aucune ne produit de passages opposés sur un même intervalle. Martin avait proposé de supprimer la seconde parce que ses deux traits se croisent sur le dessin des affectations. Lucie retire ce refus : un croisement entre traits reliant les deux listes n’est pas nécessairement un aller-retour coûteux sur la ligne des positions. Les destinations et les longueurs effectivement parcourues fournissent ici un contrôle plus précis que cette apparence.
Martin demande ensuite un second objectif, après la distance totale minimale : réduire la somme des carrés des distances individuelles. La proposition ordonnée donne quatre plus quatre, soit huit. La croisée donne neuf plus un, soit dix. Lucie choisit donc la première sous la demande nouvelle. Elle ne remplace pas le coût absolu quatre par huit ; les nombres désignent deux critères conservés dans leur ordre. Le choix final a retiré l’affectation croisée des réponses au second critère, sans lui retirer sa conformité au premier. Il distribue les déplacements en deux longueurs deux plutôt qu’en trois et un.
La préférence pour l’ordre sous ce second critère possède aussi une preuve. Pour les quatre positions a inférieur ou égal à b et c inférieur ou égal à d, le coût croisé au carré moins le coût ordonné au carré vaut 2(b−a)(d−c). Les deux différences sont multipliées entre elles, puis par deux. Cette quantité est positive lorsque les deux départs et les deux arrivées sont distincts. À zéro, un, deux et trois, elle vaut deux et retrouve dix moins huit. Lucie peut donc supprimer une inversion stricte pour diminuer ce coût quadratique, même dans un cas où l’économie en distance absolue était nulle. Les deux preuves d’échange portent sur des fonctions différentes.
Pour des listes de positions toutes distinctes, un relevé qui n’est pas ordonné possède au moins une inversion. Son échange réduit strictement la somme des carrés. L’affectation par rang est donc la seule minimale pour ce second coût. Avec des positions répétées, l’échange peut devenir nul parce que deux départs ou deux arrivées coïncident. Lucie garde alors l’unicité du tableau des positions appariées lorsqu’elle est obtenue, sans attribuer automatiquement une destination différente à chaque occurrence nommée. Dans sa première feuille à deux unités en zéro et trois places en cinq, permuter les occurrences à une même position ne change aucun des deux coûts.
Lucie conserve finalement chaque feuille avec sa demande et son relevé minimal. Les écarts cumulés pondérés par les longueurs ont certifié huit puis cinq ; les différences de moyennes donnaient une autre borne, parfois non atteinte. La construction ordonnée atteint les bornes de distance absolue, sans imposer toujours une affectation unique. Le coût quadratique peut ensuite départager des réalisations de même distance. Ces décisions appartiennent aux unités du dessin créé : elles ne certifient ni un déplacement matériel, ni une propriété des objets cités, ni un ordre de lecture réellement observé dans un livre.
Fermer le dessin change le compte aux coupures
Lucie reprend les masses de la première feuille, sans changer leurs positions zéro, deux et cinq. Une permission nouvelle referme maintenant la ligne en cercle de longueur six : le passage de cinq à zéro a une longueur un. Les unités peuvent emprunter les arcs dans les deux sens. Les départs restent deux en zéro, un en deux, un en cinq ; les arrivées une en zéro et trois en cinq. La commande conserve les unités entières et la somme des longueurs parcourues.
Martin conserve les écarts cumulés un, deux et zéro, mais Lucie ne peut plus annoncer qu’ils sont les trois passages nets imposés. Le dernier intervalle cinq–zéro peut désormais être traversé. Appelons k le passage net de zéro vers cinq sur cet arc de retour. La conservation aux trois positions donne alors les passages nets un moins k sur zéro–deux, deux moins k sur deux–cinq et moins k sur cinq–zéro, lorsque le sens positif suit zéro, deux, cinq, zéro. Chaque arc borne le coût par sa longueur multipliée par la valeur absolue de son passage net. La borne commune devient donc deux fois la valeur absolue de un moins k, plus trois fois celle de deux moins k, plus la valeur absolue de k. Fixer silencieusement k à zéro reviendrait à interdire le passage nouveau et conserverait huit. Lucie doit au contraire choisir ce même k pour les trois arcs, au lieu de minimiser leurs trois contributions indépendamment avec des circulations incompatibles.
Pour k entre un et deux, cette somme vaut quatre ; sous un, elle augmente quand k diminue, et au-dessus de deux elle augmente quand k grandit. Aucun autre k ne donne moins. Les unités entières permettent d’atteindre cette borne avec k un ou deux. Pour k un, Lucie laisse une unité en zéro et celle de cinq sur place, fait passer l’autre unité de zéro vers cinq par l’arc de longueur un, puis celle de deux vers cinq directement sur l’arc de longueur trois. Pour k deux, elle fait rejoindre zéro à l’unité de deux, sur une longueur deux, puis lui donne l’arc zéro–cinq de longueur un ; l’autre unité de zéro emploie également cet arc. Les deux préparations coûtent quatre et remplissent les arrivées. Lucie retire donc huit de la réponse au cercle et conserve deux circulations optimales, vérifiées sur leurs trois passages nets. Le choix du point où commencer le compte cumulé n’avait pas interdit de franchir ce point : c’est la variable commune k qui permet de fermer correctement la préparation.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →