Avant une rencontre, Camille prépare quatre jetons représentant des stylos et quatre places dessinées sur une fiche. Elle ne distribue aucun produit réel. Chaque jeton porte une lettre A, B, C ou D ; chaque place une lettre X, Y, Z ou W. Un nombre attaché à une association fournit un coût abstrait pour le jeu. Nora souhaite une liste complète dont la somme soit la plus petite possible, puis une preuve que le choix ne pourrait être amélioré par une autre liste.
Les quatre jetons doivent recevoir quatre places distinctes. Les lignes de la grille sont A, B, C, D ; ses colonnes X, Y, Z, W. La ligne A vaut 9, 2, 7, 8 ; B vaut 6, 4, 3, 7 ; C vaut 5, 8, 1, 8 ; D vaut 7, 6, 9, 4. Toutes les associations sont permises dans ce premier état. Les nombres ne décrivent ni un prix, ni une compétence, ni une durée ou une préférence personnelle. Ce problème d'affectation à coût minimal est classique, sans invention revendiquée.
Les pages consultées identifient seulement des stylos. Aucun prix, matériau ou usage technique n'est repris ; les associations et leurs coûts sont créés ici.
Diplomat présente des stylos : https://www.diplomat-pen.com/ .
Monteverde présente des stylos : https://monteverdepens.com/ .
Visconti présente des stylos : https://www.visconti.it/ .
Le plus petit coût libre de chaque ligne ne ferme pas la liste
Camille commence par A et choisit Y, coût deux. Pour B, elle prend ensuite Z, coût trois, meilleur que six vers X ou sept vers W parmi les places encore libres. C ne peut plus recevoir Z ; elle lui donne X, coût cinq, puis D reçoit W, coût quatre. La somme vaut quatorze. La fiche est complète et ne comporte aucune collision, mais ces propriétés ne disent pas qu'elle a atteint le plus petit total. Le choix de B a consommé la place qui ne coûtait qu'un à C.
Nora compare les deux associations B–Z et C–X, qui coûtent ensemble huit, à B–X et C–Z, qui coûtent six plus un, soit sept. Les deux places restent distinctes après cet échange. A garde Y et D garde W. La nouvelle liste coûte donc treize : deux, six, un et quatre. B reçoit une association plus chère pour sa ligne, mais le gain de C est plus grand que cette hausse. Nora choisit effectivement cette liste et retire l'annonce « le meilleur coût disponible à chaque étape donne le meilleur total ». La décision collective utilise la somme des deux changements, pas le seul changement de B.
Ce remplacement était encore possible parce que la fiche n'avait pas été remise comme définitive. La nécessité de conserver les places distinctes et le sens d'une réaffectation coordonnée avaient déjà été traités dans d'autres jeux ; ils ne constituent pas ici une nouvelle méthode. Le contrôle à développer concerne le coût du remplacement et la preuve du minimum, plutôt qu'une nouvelle promesse de couverture des quatre places.
Des nombres par ligne et par colonne donnent une borne globale
Pour certifier treize, Nora donne aux lignes les nombres deux, trois, un, quatre, puis aux colonnes les nombres trois, zéro, zéro, zéro. Pour chaque case, le nombre de sa ligne plus celui de sa colonne doit être au plus le coût inscrit. Elle vérifie cette exigence sur la grille entière, y compris les cases que sa liste n'utilise pas. Par exemple, B–X porte trois plus trois, exactement six ; C–X porte un plus trois, soit quatre, inférieur à cinq. Un nombre attribué à une colonne n'est pas un coût facturé en plus : c'est un élément de la borne qui sera comparé aux coûts originaux.
La vérification peut être donnée comme une nouvelle grille des différences. À chaque case, Nora retranche le nombre de la ligne et celui de la colonne du coût original. Elle obtient pour A : 4, 0, 5, 6 ; pour B : 0, 1, 0, 4 ; pour C : 1, 7, 0, 7 ; pour D : 0, 2, 5, 0. Aucune différence n'est négative. Cette grille conserve aussi les égalités : une différence nulle signifie que la borne atteint exactement le coût de cette case. Nora ne confond pas « différence nulle » et « association gratuite » : B–X coûte toujours six sur la fiche à remettre.
Dans toute liste complète, chaque ligne intervient exactement une fois et chaque colonne également. En additionnant les quatre inégalités des cases retenues, Nora retrouve donc une fois chacun des nombres de ligne et de colonne. Leur somme vaut deux plus trois plus un plus quatre, puis trois : treize. Les différences restantes sont toutes positives ou nulles. Toute liste complète coûte donc au moins treize, quel que soit son ordre de préparation. La liste A–Y, B–X, C–Z, D–W atteint cette borne ; aucun autre choix ne peut avoir un total douze. Nora remet ensemble la réalisation et cette borne, sans demander au lecteur de comparer seulement quelques alternatives choisies.
La même décomposition révèle ce qui manque à la première fiche. A–Y, B–Z et D–W ont une différence nulle, mais C–X porte une différence un. Son total est exactement la borne treize plus ce reste un, donc quatorze. Nora peut localiser le dépassement dans la grille de contrôle, même si B avait été le premier choix qu'elle a modifié pour réparer. Le reste sur C–X et la décision d'échanger deux cases ne se contredisent pas : les différences décrivent les coûts sous un certificat, tandis que l'échange doit conserver une place distincte pour chaque jeton.
Les zéros doivent encore former une liste entière
Pour atteindre treize, les quatre différences choisies doivent toutes être nulles. A ne possède qu'un zéro, vers Y ; C qu'un zéro, vers Z. Après ces deux choix, B ne peut plus utiliser son zéro vers Z et doit prendre son autre zéro, vers X. D prend alors W. Ces contraintes déterminent une seule liste atteignant la borne. Nora vérifie ainsi l'unicité de son minimum dans cette grille, au lieu de la déduire de l'unicité du premier zéro qu'elle aurait rencontré pendant sa recherche.
Une proposition choisissant A–Y, B–Z, C–Z et D–W n'est pas une seconde solution de coût treize : elle attribue deux jetons à Z. Les zéros sont des cases candidates, pas quatre associations déjà compatibles. Le fait qu'une ligne contienne un zéro ne suffit pas à construire une liste complète de zéros. Ce garde-fou de couverture reste bref, car le défaut de places partagées avait déjà été rempli ailleurs. Nora conserve ici le lien précis avec le certificat : c'est une liste entière de zéros qui rejoint la borne de coût, pas quatre minima de lignes pris sans leurs colonnes.
Un cycle de différences nulles peut laisser deux minima
Nora prépare une branche qui modifie seulement B–Z : son coût descend de trois à deux. Toutes les autres cases restent celles de la première grille. L'ancienne liste A–Y, B–X, C–Z, D–W coûte encore treize. La liste issue des choix successifs coûte désormais deux plus deux plus cinq plus quatre, également treize. Il reste pourtant à établir que ces deux listes sont bien minimales, et non deux valeurs égales que dépasserait une troisième proposition.
Le certificat précédent ne convient plus à toutes les cases : le nombre trois de B plus zéro de Z dépasse le nouveau coût deux. Nora conserve cet échec, puis construit un autre certificat. Les nombres de ligne deviennent deux, deux, un, trois ; ceux de colonne quatre, zéro, zéro, un. Leur somme vaut encore treize. Les différences sont maintenant A : 3, 0, 5, 5 ; B : 0, 2, 0, 4 ; C : 0, 7, 0, 6 ; D : 0, 3, 6, 0. Elles sont toutes non négatives. Les deux listes de coût treize ne sont donc pas seulement égales : elles atteignent une nouvelle borne qui couvre cette grille révisée.
Dans les deux listes, A reçoit Y et D reçoit W. B et C se partagent X et Z. Les quatre cases B–X, B–Z, C–X et C–Z ont maintenant des différences nulles. Passer d'une diagonale de ce petit rectangle à l'autre conserve la présence de chaque ligne et de chaque colonne, ainsi que le coût total. Nora représente ce passage par le cycle B, X, C, Z, B. Ce cycle décrit deux listes complètes alternatives ; elle ne l'exécute pas comme quatre attributions supplémentaires. Le coût nul du changement signifie qu'il ne départage pas les deux listes.
Nora retient la première pour la remise, mais retire son ancien qualificatif « minimum unique ». Toutes les listes minimales doivent encore utiliser A–Y ; après ce choix, D doit prendre W, puisque X et Z seront utilisés par B et C. Il ne reste que les deux diagonales du rectangle. Le dossier conserve donc exactement deux listes minimales. Le mécanisme à garder n'est pas la seule baisse d'un chiffre : cette baisse a ouvert un cycle de cases à égalité et changé le statut d'unicité de la réponse. La fiche originale reste unique sous son ancien coût B–Z égal à trois.
La plus grande case et la somme ne choisissent pas la même remise
Une commande séparée reprend la grille originale et demande de réduire le coût le plus élevé parmi les quatre associations, plutôt que leur somme. Nora peut comparer les deux listes déjà obtenues, mais elle doit de nouveau justifier le meilleur niveau permis par cette commande. Quatre petites cases et un total réduit ne sont pas des exigences identiques.
Si le plus grand coût autorisé était quatre, aucune case de la colonne X ne serait possible : elle contient neuf, six, cinq, sept. Une liste complète manquerait cette place. Le niveau doit donc atteindre au moins cinq. À cinq, C–X devient possible, A prend Y, B prend Z et D prend W. Les coûts valent deux, trois, cinq, quatre : leur maximum est cinq et leur somme quatorze. Nora atteint la borne cinq et choisit cette liste pour la nouvelle commande. La colonne X doit être remplie malgré son coût minimal plus grand que ceux d'autres colonnes.
La liste de somme minimale treize utilisait B–X à six. Son coût le plus élevé dépasse donc le minimum cinq de cette nouvelle commande. Nora ne corrige pas un défaut de cette ancienne liste : elle choisit un autre objectif et une autre remise. Pour la somme, remplacer B–X et C–Z par B–Z et C–X ajoutait un au total ; pour le plus grand coût, ce remplacement supprimait le six et laissait cinq comme plafond. Elle transmet ces deux changements avec leurs critères. La phrase « prendre les associations les moins chères » ne suffirait pas à indiquer laquelle des deux fiches doit être utilisée.
À ce niveau cinq, A ne peut recevoir que Y parmi les places que les autres choix laissent disponibles ; plus directement, A n'a que sa case Y sous le plafond. X n'est permis qu'à C, et W seulement à D. B reçoit donc Z. Le contrôle de faisabilité à ce seuil ferme cette réalisation. Les outils de couverture étaient déjà connus ; nous ne les créditons pas comme une nouvelle procédure. Ils vérifient ici que la fiche à plafond cinq est effectivement complète, avant de lui joindre son total quatorze.
Décaler une ligne est neutre seulement si elle reste obligatoirement présente
Sur la grille originale, Nora ajoute sept à chaque coût réel de la ligne C. Toute liste complète utilise exactement une case de cette ligne : tous ses totaux augmentent donc exactement de sept. L'ordre entre les vingt-quatre listes complètes ne change pas, et l'ancien minimum treize devient vingt. Le nombre ajoute un coût constant aux réponses complètes ; il ne les transforme pas en réponses à un autre classement de préférences.
Nora ouvre ensuite une possibilité différente : C peut rester sans place, avec une pénalité fixée à huit ; A, B et D doivent toujours recevoir trois places distinctes. Une place restera alors inutilisée. La pénalité est une règle du jeu, pas le prix d'un stylo absent. Elle est ajoutée à la somme lorsque C n'est pas affecté. La comparaison doit tenir compte à la fois des listes complètes et de ces listes partielles explicitement autorisées.
Sans C, Nora choisit A–Y à deux, B–Z à trois et D–W à quatre. Ces trois associations coûtent neuf ; avec la pénalité huit, la réponse coûte dix-sept. Ce neuf est minimal pour les trois lignes : leurs minima respectifs deux, trois et quatre sont atteints à trois colonnes distinctes, donc ils fournissent simultanément une borne et une réalisation. Sous la grille originale, la liste complète à treize gagne contre toute réponse sans C à dix-sept. Nora affecte donc C à Z et B à X dans la remise retenue, en conservant la possibilité de refus comme possibilité réellement comparée, et non comme action choisie.
Après le supplément sept sur toutes les cases réelles de C, les listes complètes ont au moins vingt, tandis que la réponse sans C garde dix-sept. Nora choisit maintenant de ne pas affecter C ; X reste inutilisée, A–Y, B–Z et D–W sont remis. Le supplément de ligne a donc changé la réponse active, même s'il conservait l'ordre entre toutes les listes complètes. Il ne s'appliquait pas à la pénalité de non-affectation. Le raisonnement « tout total reçoit sept » avait cessé d'être vrai pour l'ensemble des réponses autorisées, parce qu'une branche ne choisissait plus aucune case réelle de C.
Une réduction de ligne ne doit pas oublier la non-affectation
Camille essaie de normaliser cette dernière grille en retirant huit de chaque case réelle de C, dont le minimum augmenté était huit. Pour une liste complète, elle obtient le coût original diminué de un : le meilleur total affiché devient douze. Elle laisse pourtant la pénalité de non-affectation à huit ; la meilleure liste sans C affiche toujours dix-sept. La grille ainsi modifiée ferait choisir une liste complète, alors que la demande réelle choisissait la non-affectation à dix-sept contre vingt. Nora refuse cette réduction comme comparaison commune aux deux branches.
Le défaut ne vient pas du signe d'une case réduite : elles restent positives ou nulles. Il vient d'un montant retiré aux seules réponses utilisant C. La liste complète gagne artificiellement huit sur son total affiché ; la liste sans C ne reçoit pas cette diminution. Ajouter huit après avoir choisi la liste complète donnerait vingt, mais ne réparerait pas le choix déjà effectué : la réponse à dix-sept avait été écartée sous des totaux non comparables. Nora retire donc la promesse « on peut rétablir les montants après sélection et garder forcément le meilleur choix ». La transformation doit préserver la comparaison avant la sélection.
Elle répare le tableau en traitant aussi la non-affectation comme une case de C, attachée à une colonne fictive qui ne consomme aucune des quatre places réelles. Son coût initial est huit. Retirer huit à toutes les options de C réduit alors également cette case à zéro. La meilleure liste complète affiche douze ; la liste avec C non affecté affiche neuf. Nora choisit cette dernière, puis rétablit huit pour retrouver dix-sept. Les deux familles de réponses avaient cette fois reçu la même diminution, car chacune sélectionnait exactement une option de C, réelle ou fictive. La colonne ajoutée représente une permission donnée, pas un cinquième stylo ou une place matérielle.
Cette représentation doit encore préserver la différence entre une place libre et une pénalité payée. Dans la liste retenue, X est libre et C reçoit l'option fictive ; aucun autre jeton ne reçoit cette option dans les données de cette branche. Nora transmet explicitement A–Y, B–Z, D–W et C sans place, avec les neuf de leurs associations et les huit de pénalité. Une fiche ne montrant que trois zéros et une case fictive à zéro oublierait les coûts originaux. Les nombres réduits avaient permis la sélection ; les nombres remis décrivent la réponse effectivement choisie.
Une liste et son certificat conservent la même demande
Nora garde les feuilles séparées : somme minimale originale treize, deux minima treize sous le coût révisé, plus grand coût minimal cinq avec total quatorze, puis non-affectation à dix-sept lorsque la ligne C reçoit le supplément. Chaque choix possède sa grille, son objectif et les options qu'il autorise. Les stylos représentés ne fournissent aucun de ces nombres. La fiche permet seulement de vérifier une affectation créée et la portée de son certificat, sans transformer un calcul sur papier en distribution réelle.