Nora prépare une feuille où plusieurs demandes peuvent partager un groupe, à condition de ne pas être incompatibles. Elle possède toutes les incompatibilités avant de commencer, mais sa première procédure attribue les demandes une par une. Choisir chaque fois le premier groupe encore possible paraît économe. Nous allons remplir ce classement, puis regarder les changements nécessaires pour remettre une feuille plus courte. L'ordre des choix et le minimum final ne seront pas annoncés comme une seule propriété.
Les demandes sont six cartes fictives, A1, A2, A3, B1, B2 et B3. Un groupe peut recevoir autant de cartes que nécessaire, sauf lorsqu'un trait interdit une paire. Chaque carte doit rejoindre exactement un groupe. Les numéros des groupes sont des étiquettes, pas des heures ni des places matérielles. Aucun service réellement exécuté, durée, personnel ou capacité alimentaire n'est mesuré. Les principes de coloration et de classement glouton sont classiques ; nous ne revendiquons pas leur invention.
LAMY se présente comme fabricant d'instruments d'écriture.
Pelikan présente une catégorie d'écriture.
Kaweco présente un stylo-plume.
Ces pages situent seulement des outils d'écriture. Elles ne donnent ni les incompatibilités ni la procédure de nos cartes.
Attribuer au premier groupe possible
Notre liste de conflits donne A1 avec B2 et B3, A2 avec B1 et B3, A3 avec B1 et B2. Elle contient ces six paires et aucune autre. Les cartes A ne se gênent pas entre elles, les cartes B non plus. Chaque Ai est également compatible avec le Bi portant le même indice. La règle de Nora reçoit une carte, examine les groupes un, deux, trois dans cet ordre et l'inscrit dans le premier qui ne contient aucune de ses voisines incompatibles. Elle crée un groupe seulement quand tous les groupes déjà ouverts sont interdits pour cette carte.
Nora choisit l'ordre A1, B1, A2, B2, A3, B3. A1 ouvre le groupe un. B1 n'est pas incompatible avec A1 et rejoint ce même groupe. A2 ne peut plus y entrer, puisque B1 y est présente et la paire A2-B1 appartient à notre liste ; A2 ouvre le groupe deux. B2 échoue dans le premier à cause d'A1, mais rejoint le deuxième parce qu'elle ne gêne pas A2. Les quatre premières décisions donnent donc A1 avec B1, puis A2 avec B2.
A3 rencontre maintenant deux refus distincts : B1 interdit le premier groupe et B2 le deuxième. Elle ouvre le troisième. B3 ne peut pas rejoindre A1 dans le premier ni A2 dans le deuxième, mais elle est compatible avec A3 et rejoint le troisième. La feuille complète contient trois groupes : A1,B1 ; A2,B2 ; A3,B3. Tous les conflits relient des groupes différents. La procédure a bien conservé les choix antérieurs au moment où elle a cherché une place pour chacune des deux dernières cartes.
Nora vérifie ce que ces deux refus prouvent réellement. A3 ne possédait aucune place dans les deux groupes déjà composés ; cela ne dit pas que les six cartes seraient impossibles à placer dans deux groupes autrement composés. La procédure n'avait pas permis de sortir B1 ou B2 pour rouvrir une place. Elle a choisi un nouveau groupe sous ses engagements locaux. Nora conserve trois comme résultat de cette exécution, mais retire la légende « minimum pour toute la liste » avant d'avoir comparé une autre attribution complète.
Elle prépare justement tous les A ensemble dans le premier groupe et tous les B dans le deuxième. Aucun groupe ne contient une paire de la liste : toutes les paires interdites vont d'un A vers un B. Deux groupes suffisent. Un seul ne conviendrait pas, puisqu'il réunirait notamment A1 et B2, effectivement incompatibles. Nora retient donc deux comme minimum libre pour cette liste. La réussite de la procédure à trois reste dans l'historique, avec un autre intitulé : elle respectait les conflits, mais avait ouvert un groupe de plus que nécessaire.
Deux groupes entiers ne peuvent pas simplement être réunis
Camille essaie de raccourcir la première feuille sans séparer les trois couples qu'elle contient. Réunir A1,B1 avec A2,B2 placerait A1 et B2 ensemble, ainsi qu'A2 et B1 : deux conflits. Réunir le premier couple avec A3,B3 produirait A1-B3 et A3-B1. Réunir le deuxième avec le troisième produirait A2-B3 et A3-B2. Les trois réunions de deux groupes échouent. Aucune n'est écartée seulement parce que Nora préférait garder ses anciens numéros.
Cela n'empêche pas la remise à deux déjà remplie. Celle-ci a séparé chaque couple Ai,Bi, en regroupant les trois A d'un côté et les trois B de l'autre. Nora retire donc une note qui déduisait du refus des trois réunions que deux groupes étaient impossibles. Les réunions avaient examiné un menu plus étroit : conserver entières les classes de la première feuille. Le nouveau menu permet de réattribuer les cartes séparément. Les deux groupes gagnés n'apparaissent qu'après ce changement effectif d'organisation.
Pour remettre les groupes A dans le numéro un et B dans le numéro deux, Nora change quatre cartes de la feuille initiale. A2 passe de deux à un, A3 de trois à un, B1 de un à deux et B3 de trois à deux. A1 reste en un et B2 reste en deux. La remise finale se lit A1,A2,A3 puis B1,B2,B3. Nora ne compte pas trois déplacements au motif qu'il y avait trois groupes à reprendre. Les interventions portent sur quatre cartes identifiées, et le groupe trois devient vide après les deux sorties d'A3 et B3.
Camille demande si une autre correction pourrait changer moins de quatre cartes en terminant dans deux groupes. Nora suit les conflits dans un parcours qui relie les six cartes : A1-B2-A3-B1-A2-B3-A1. Avec seulement deux groupes, chaque voisinage force une alternance. Une fois le groupe d'A1 choisi, B2 prend l'autre, A3 rejoint A1, B1 rejoint B2, A2 rejoint A1 et B3 rejoint B2. Toute remise à deux rassemble donc exactement les trois A face aux trois B, à échange des noms de groupes près.
Sur la première feuille, chaque Ai portait le groupe i et chaque Bi le même groupe i. Si les trois A terminent ensemble dans un groupe nommé k, au plus un A peut garder son ancien numéro : Ak, si k est l'un de un, deux ou trois. Les trois B terminent dans un autre groupe nommé l et au plus un B conserve son numéro. Au maximum deux cartes demeurent donc inchangées, sur six. Au moins quatre doivent changer. Nora atteint cette borne avec sa correction précédente ; quatre est le minimum des réattributions, pas seulement leur nombre dans un essai choisi.
Nora peut choisir les numéros un et trois plutôt que un et deux pour la remise finale. A1 et B3 resteraient alors à leurs anciens numéros, et quatre autres cartes changeraient encore. Cette possibilité ne réduit pas le minimum : elle déplace les deux identités conservées. Nora garde un et deux pour sa feuille active. Nous laissons ce départage bref, sans faire de chaque renommage de groupes une nouvelle correction de fond ; le regroupement nécessaire sépare toujours les A des B.
Un autre ordre évite les corrections de la première feuille
Nora recommence une préparation indépendante avec la même règle du premier groupe possible, mais reçoit toutes les cartes A avant les B : A1, A2, A3, B1, B2, B3. Les trois A rejoignent successivement le groupe un, puisque leurs paires ne figurent pas dans les conflits. B1 ne peut y entrer à cause d'A2 et d'A3 ; elle ouvre le groupe deux. B2 et B3 y rejoignent B1, car aucune paire de deux B n'est interdite. Le résultat contient seulement deux groupes, sans correction après leur attribution.
Cette deuxième exécution fournit la même remise minimale que la réparation, avec d'autres actes de préparation. Elle ne change ni les six cartes ni leurs six incompatibilités ; elle change l'ordre dans lequel la procédure les a reçues. Nora choisit cet ordre pour une feuille encore entièrement libre. Elle ne le présente pas comme l'ordre qui avait été utilisé auparavant : l'exécution A1,B1,A2,B2,A3,B3 avait déjà posé des cartes dans trois groupes. Les deux traces sont conservées séparément, avec leur résultat et les interventions qu'elles ont ou non demandées.
L'ordre des arrivées n'est pas une donnée réelle à prévoir dans cet atelier. Nora l'a choisi avant la préparation. Si une autre commande lui imposait de traiter les cartes dans l'ordre entrelacé sans revoir les anciennes places, la deuxième exécution ne lui appartiendrait pas. La méthode ne lui promet donc pas deux groupes pour tous les ordres possibles. Le choix de tous les A d'abord répond à la liberté donnée dans cette branche, plutôt qu'à une affirmation selon laquelle la procédure détecterait toujours le minimum même lorsqu'elle reçoit les cartes autrement.
Quatre premières places fixées changent le travail restant
Une autre scène conserve seulement les quatre premières inscriptions de la première exécution : A1 et B1 dans le groupe un, A2 et B2 dans le groupe deux. A3 et B3 n'ont pas encore de place. L'hôte interdit de modifier ces quatre inscriptions. A3 est incompatible avec B1 et B2 et ne peut donc rejoindre aucun des deux groupes conservés. B3 rencontre A1 et A2 et les refuse également. Nora place les deux dernières cartes dans un troisième groupe. Aucun autre choix sur les seules cartes restantes ne peut finir en deux.
Cette impossibilité restante ne contredit pas le minimum libre deux calculé au départ. Les quatre inscriptions conservées ont retiré les deux regroupements qui réuniraient tous les A et tous les B. Nora ne donne pas à A3 les anciennes places de B1 ou B2 en retirant discrètement leurs cartes de la scène. Elle conserve trois pour cette commande sans modification du préfixe. La distinction entre la préparation libre et les places désormais fixées reste un cadre bref ; la réponse suivante autorise des interventions déterminées et les compte réellement.
L'hôte autorise alors à corriger des inscriptions parmi ces quatre, et demande le plus petit nombre de cartes à réattribuer pour finir en deux groupes. Nora change A2 de deux vers un et B1 de un vers deux. Les quatre premières places deviennent A1,A2 dans le premier et B1,B2 dans le second. Elle ajoute A3 au premier, B3 au second. Deux réattributions ont suffi avant ces deux placements nouveaux. Elle ne compte pas les nouvelles places d'A3 et de B3 comme corrections, puisque ces cartes n'en possédaient pas encore.
Une seule correction ne pourrait suffire. Dans toute remise à deux, les A doivent partager un groupe et les B l'autre, comme le parcours des six conflits l'avait imposé. Or les deux A déjà inscrits possèdent des numéros différents, de sorte qu'au moins l'un doit changer. Les deux B inscrits sont eux aussi séparés, demandant au moins un changement d'un B. Ce sont deux cartes distinctes. Nora a donc une borne de deux et une réalisation qui l'atteint. La commande restante modifie moins de cartes que la réparation de la feuille entière, parce que deux inscriptions n'avaient pas encore été effectuées.
Camille choisit une autre réalisation à deux corrections : A1 rejoint A2 dans le groupe deux et B2 rejoint B1 dans le groupe un. A3 reçoit alors deux, B3 un. Nora peut accepter cette réalisation, mais conserve la première sur sa feuille active. Les cartes corrigées y sont A2 et B1. Le nombre minimal ne lui donne pas, à lui seul, ces deux noms ; le choix de conserver les numéros d'A1 et de B2 les désigne ici. Ce rappel reste séparé de la preuve qui interdisait une seule correction.
Le nombre de voisines borne cette procédure sans donner le minimum
Chaque carte du premier dessin possède deux voisines incompatibles. Lorsqu'une nouvelle carte est reçue, chacune de ses voisines déjà placées peut lui interdire au plus un numéro de groupe. Même si les deux occupent des groupes différents, au maximum deux numéros sont interdits. Parmi un, deux et trois, il reste donc un groupe possible. La procédure du premier groupe disponible ne peut ouvrir un groupe quatre sur cette liste, quel que soit l'ordre dans lequel Nora lui remet les six cartes.
L'ordre entrelacé montre que trois peut effectivement être atteint : les deux voisins d'A3 se trouvaient dans un et deux, puis ceux de B3 également. Trois est donc un maximum possible pour cette procédure sur notre liste, tandis que deux demeure le minimum possible pour une préparation libre. Nora conserve les deux nombres avec leurs questions. Le compte de voisines a borné les groupes que la procédure pourrait ouvrir ; il n'a pas obligé toute remise valide à atteindre cette borne. Deux et trois décrivent ici deux propriétés différentes du même dessin.
Nora peut étendre la même raison à une liste où aucune carte ne possède plus de d voisines. Au moment de son placement, au plus d numéros peuvent être interdits, laissant un choix parmi les d plus un premiers numéros. Cette borne décrit la procédure locale même si des voisines ne sont pas encore placées. Elle ne lui donne pas le meilleur regroupement global. Dans notre liste à deux voisines au maximum, l'exécution à trois a précisément atteint d plus un, alors qu'une autre exécution pouvait se contenter de deux.
Une famille de dessins accentue le même écart de méthode
Nora compose maintenant huit cartes, A1 à A4 et B1 à B4. Chaque Ai gêne les Bj dont l'indice diffère du sien, mais aucune paire de A, aucune paire de B et aucune paire Ai,Bi n'est interdite. Le dessin possède donc trois voisines par carte. Elle remet les cartes dans l'ordre A1,B1,A2,B2,A3,B3,A4,B4, sous la même procédure locale. Les trois premiers couples ouvrent un, deux et trois comme auparavant, mais le quatrième couple donne cette fois une conséquence supplémentaire.
A4 trouve dans les trois groupes B1, B2 et B3, qui lui sont tous incompatibles. Elle ouvre le groupe quatre. B4 ne peut rejoindre A1, A2 ou A3 dans les trois précédents, mais peut partager le quatrième avec A4. Nora obtient quatre couples, chacun dans son groupe. Elle pourrait pourtant réunir tous les A dans un et tous les B dans deux : les mêmes règles de conflits le permettent encore. Le groupe supplémentaire vient de l'exécution de la procédure sur des classes déjà composées, pas d'un conflit entre les deux cartes du quatrième couple.
Le mécanisme se prolonge pour n couples avec n au moins égal à trois. Supposons que les k premiers couples portent déjà les groupes un jusqu'à k. La carte A suivante est incompatible avec tous les B de ces k couples ; chacun interdit l'un des k numéros. Elle doit ouvrir k plus un. Le B de même indice est incompatible avec tous les A antérieurs, mais pas avec cette A nouvelle ; il rejoint son numéro k plus un. À partir du premier couple dans un, cette étape impose successivement n groupes pour l'ordre entrelacé.
Tous les A ensemble et tous les B ensemble donnent pourtant deux groupes pour chaque dessin de cette famille. Le nombre de voisines vaut n moins un, et la procédure entrelacée atteint sa borne n. Il n'existe donc pas de nombre fixe de groupes supplémentaires qui couvrirait son écart au minimum sur toute cette famille : pour n couples, elle ouvre n moins deux groupes de trop. Nora ne transforme pas cette comparaison en un relevé de services réels plus longs. Elle a établi une limite de sa méthode locale, avec une construction qui produit effectivement chacun des états intermédiaires nécessaires.
Les numéros autorisés ne sont plus de simples noms interchangeables
Une dernière branche conserve les six conflits et donne à chaque carte une liste de numéros autorisés. A1 accepte seulement un ; A2 accepte un ou deux ; A3 seulement deux. B1 accepte un ou trois ; B2 deux ou trois ; B3 seulement trois. Ces listes sont des permissions de l'exercice, pas des salles réellement disponibles. Elles s'ajoutent aux conflits : deux cartes compatibles doivent encore avoir le droit d'utiliser le numéro qu'on leur attribue. On ne peut donc plus renommer librement un groupe sans vérifier chaque carte qu'il contient.
Nora compose le groupe un avec A1 et A2, le deuxième avec A3, le troisième avec B1, B2 et B3. Les cartes A ne se gênent pas entre elles, les B non plus, et chacune possède son numéro dans sa liste. Toutes les paires interdites ont encore des numéros différents. Trois groupes suffisent donc sous ces permissions. La feuille libre à deux, avec tous les A en un et tous les B en deux, ne convient plus : A3 ne peut utiliser un, et B1 comme B3 ne peuvent utiliser deux. Le refus ne vient pas de conflits nouveaux.
Une autre remise à deux ne pourrait pas contourner ces deux absences en choisissant d'autres noms de groupes. Le parcours de conflits impose toujours que tous les A partagent un numéro et tous les B un autre. Pour les A, il faudrait alors un numéro présent dans les trois listes : un seulement pour A1, un ou deux pour A2, deux seulement pour A3. Leur intersection est vide. A1 et A3 ne sont pourtant pas directement incompatibles ; c'est leur appartenance nécessaire au même côté dans toute remise à deux qui fait rencontrer leurs permissions disjointes. Trois devient ainsi le minimum autorisé, même si le dessin sans ces listes se contentait de deux.
L'hôte modifie ensuite une permission précise : A3 peut aussi utiliser un, tout en conservant deux. Les trois listes A possèdent maintenant un en commun. Les trois listes B possèdent trois en commun : B1 l'autorise, B2 également et B3 le demandait déjà. Nora remet donc tous les A en un et tous les B en trois. Deux groupes sont utilisés ; le numéro deux demeure libre. Elle ne compte pas trois groupes parce que le plus grand numéro inscrit est trois. Le calcul porte sur les groupes effectivement occupés, et la paire A1-B2 toujours interdite empêche encore de n'en utiliser qu'un.
Pour passer de sa première remise à trois groupes à cette nouvelle remise à deux, Nora déplace seulement A3 de deux vers un. Toutes les autres cartes conservent leur numéro. Un changement suffit, et zéro ne suffirait pas : sans déplacer de carte, le groupe deux resterait occupé par A3, avec les groupes un et trois encore présents. Nora inscrit donc une réattribution minimale avec la permission qui l'a rendue possible. Elle ne prétend pas avoir découvert après coup que l'ancien classement à trois pouvait déjà tenir en deux sous les listes antérieures.
Camille applique également la procédure locale à la liste autorisée avant cette modification, en donnant tous les A d'abord. A1 et A2 utilisent un, A3 doit ouvrir deux. B1 refuse un à cause d'A2 et ouvre trois, seul autre numéro qu'elle accepte. B2 ne peut rejoindre deux à cause d'A3, mais rejoint trois ; B3 y rejoint ses deux voisines de catégorie B. Cette exécution atteint trois, le minimum des permissions initiales. La même taille trois provenait d'un défaut d'ordre dans notre première feuille sans listes ; elle correspond maintenant à une borne réelle des listes. Nora garde chacune avec sa preuve plutôt qu'avec un verdict commun sur le chiffre trois.
Nora garde finalement l'ordre de tous les A avant les B pour son projet libre à six cartes. Les feuilles déjà composées conservent leurs propres corrections : quatre cartes changent dans la remise complète, deux parmi les quatre premières si les deux dernières n'ont pas encore été placées, aucune si l'ordre favorable est choisi dès le départ. Les demandes et les conflits sont restés identifiés. Le dossier ne confond donc pas un classement recevable, le nombre de groupes qu'une procédure peut ouvrir et les interventions nécessaires pour atteindre le regroupement qu'elle souhaite remettre.