Un stock assez grand pour toute la table peut laisser plusieurs personnes dépendre des mêmes pièces. Chacune voit deux choix, mais les choix de trois noms peuvent réunir seulement deux objets. Pour préparer une attribution sur papier, Nora souhaite repérer cette difficulté avant de promettre une assiette à chacun. Elle veut aussi savoir quand une place occupée peut être libérée par une suite de changements, au lieu de traiter tout objet déjà inscrit comme définitivement indisponible.
Nous créons cinq personnes A, B, C, D et E, ainsi que des jetons représentant des assiettes. Chaque identité d’assiette ne peut être attribuée qu’une fois ; chaque personne doit recevoir une identité qu’elle accepte dans la table donnée. Les acceptations n’ont aucun ordre de préférence. Elles ne représentent ni allergie, ni besoin alimentaire, ni propriété d’une vaisselle réelle. Aucun service matériel n’a lieu. Les petits modèles d’affectation sont classiques, sans invention revendiquée. Nous cherchons le nombre de personnes pouvant être servies, puis des listes qui l’atteignent.
Duralex propose des assiettes.
Pillivuyt propose des assiettes.
Gien propose des assiettes.
Ces pages ont été consultées textuellement pour ces seules catégories. Elles ne fournissent aucune acceptation de notre groupe. Nous n’avons examiné ni image, ni dimension, ni résistance des produits. Le contrôle porte sur des identités et des associations créées ; une catégorie commerciale ne donne pas à un jeton une capacité supplémentaire ou un destinataire obligé.
Compter les choix d’un groupe plutôt que ceux de chaque nom
Les cinq assiettes portent les numéros un à cinq. A, B et C acceptent chacun un ou deux. D accepte trois ou quatre ; E accepte quatre ou cinq. Toutes ces possibilités sont données, et aucune autre ne l’est dans cette première branche. Nora demande une assiette distincte pour chaque personne. La même identité deux ne pourrait donc pas être remise à B et à C, même si leurs deux acceptations la mentionnent.
Camille annonce que la demande est réalisable : cinq assiettes sont présentes pour cinq personnes, chacune dispose de deux possibilités, et chaque assiette apparaît dans au moins une liste. Nora examine pourtant ensemble A, B et C. Leurs six mentions ne désignent que deux identités, un et deux. Même en choisissant différemment pour chacun, au plus deux de ces trois noms peuvent recevoir une identité distincte dans cet ensemble. Nora retire donc la promesse d’une liste complète. Le défaut ne tient à aucun destinataire sans choix ni à une assiette oubliée du stock total ; il apparaît seulement quand les choix partagés sont réunis sans compter leurs répétitions.
Le groupe fournit également une limite sur toute attribution partielle. Au moins l’un de A, B et C restera sans identité ; les deux autres personnes ne peuvent ajouter que deux noms servis. Le maximum total est donc au plus quatre. Nora atteint cette limite avec B à un, C à deux, D à trois et E à quatre, laissant A sans attribution et cinq libre. Elle retient quatre comme maximum vérifié. L’assiette cinq n’annule pas le déficit du groupe, puisqu’aucun de ses trois membres ne l’accepte. La présence d’une pièce libre ne prouve donc pas qu’elle puisse compléter la liste inachevée.
Nora pourrait laisser B sans attribution plutôt que A, en donnant un à A et deux à C. Elle pourrait aussi laisser C sans attribution. Aucun des trois noms n’est condamné individuellement par les listes : chacun figure dans une attribution de quatre. Ce qui est impossible est de les servir tous ensemble avec deux identités. Nora retire ainsi le titre « A ne peut pas recevoir d’assiette » de sa première fiche partielle. Elle garde une insuffisance portant sur le groupe, sans la transformer en une propriété personnelle du nom momentanément absent de la réalisation choisie.
Une recherche bloquée peut désigner précisément ce qui manque
Partons de B à un, C à deux, D à trois et E à quatre. Nora cherche une place pour A sans modifier les acceptations. Un et deux sont occupés. Elle ne les écarte pourtant pas immédiatement : elle examine si leur destinataire actuel peut recevoir une autre assiette, pour libérer celle dont A aurait besoin. Le projet n’a encore produit aucune remise irréversible ; ces lignes sont une préparation modifiable.
Depuis A, les recherches vers un et deux rencontrent B et C. Depuis B, les seules possibilités reviennent à un et deux ; il en va de même depuis C. Nora conserve les noms et les identités effectivement atteints : A, B, C d’un côté, un et deux de l’autre. Aucun de ces parcours ne rejoint trois, quatre ou cinq. Refaire la recherche depuis B avec l’espoir qu’un nouveau commencement ouvrira une sortie ne change pas ces listes. Nora ferme cette tentative après avoir retrouvé tous les choix des trois personnes atteintes, plutôt que laisser une boucle entre les deux assiettes passer pour une réparation en cours.
Ce relevé explique le blocage sans dépendre du choix B–un, C–deux. Tous les choix des personnes atteintes sont contenus dans les identités atteintes. Ces deux identités ont déjà deux destinataires dans le relevé ; A vient s’ajouter comme troisième personne qui voudrait entrer. Nora retrouve ainsi le même déficit de un depuis sa tentative de réparation. Le contrôle n’affirme pas qu’aucune autre liste de quatre ne serait possible. Il montre pourquoi changer seulement les places de B et C, ou recommencer dans l’autre ordre, ne créera pas une troisième identité acceptable pour ce groupe.
Camille propose de suivre A vers un, B vers deux, C vers un, puis d’appeler cette boucle trois changements accomplis. Nora refuse : un resterait demandé à la fois par A et C. Une boucle d’associations ne possède ici aucune identité libre où commencer une redistribution sans collision. Elle conserve les deux choix de B et C comme possibilités, sans en faire trois places. Le relevé atteint sert donc à distinguer un cycle qui conserve le manque d’une suite qui pourrait réellement se terminer sur une ressource libre. Une longueur de parcours plus grande ne fournit pas à elle seule cette différence.
Une possibilité nouvelle ouvre une suite jusqu’à l’assiette libre
Une branche nouvelle ajoute trois à la liste de A ; les autres acceptations restent celles du départ. Nora conserve la préparation B–un, C–deux, D–trois, E–quatre pour rechercher une extension. Elle ne commence pas par libérer D ou E sans destination. L’association A–trois devient possible dans cette branche, mais trois reste déjà occupée dans l’état à compléter.
La recherche depuis A peut maintenant rencontrer trois, puis D. D accepte quatre, qui appartient à E ; E accepte cinq, encore libre. Nora retient cette suite précise : A, trois, D, quatre, E, cinq. Elle ne se contente pas d’ajouter A auprès de trois dans l’ancienne liste. Elle prépare E à cinq, puis D à quatre, enfin A à trois. B garde un et C deux. Chacune des trois nouvelles associations est permise, leurs identités sont distinctes et les deux changements de destinataires déjà inscrits libèrent successivement ce dont la personne précédente a besoin. La suite atteint une assiette libre au lieu de revenir sur la première.
La redistribution a remplacé D–trois et E–quatre par D–quatre et E–cinq, puis ajouté A–trois. Trois associations entrent dans la nouvelle liste, deux en sortent ; une personne servie de plus apparaît. Nora remet A–trois, B–un, C–deux, D–quatre, E–cinq. Le maximum est désormais cinq, puisque les cinq personnes ont chacune une assiette. Elle garde toutefois les deux remplacements dans le relevé de correction. Dire qu’une seule association acceptable a été ajoutée aux possibilités ne signifie pas qu’une seule ligne de la préparation a changé : la nouvelle sortie a exigé une redistribution dans les lignes déjà occupées.
Camille compare une tentative qui aurait déplacé D de trois vers quatre en laissant E à quatre. Nora l’écarte avant de l’utiliser. Elle conserve la fin libre cinq et prépare les changements depuis cette fin : E la reçoit, puis quatre peut recevoir D, puis trois A. Le sens de lecture de la recherche et l’ordre de mise à jour choisi ne sont donc pas identiques. La recherche explique qui doit pouvoir changer pour atteindre cinq ; la mise à jour libère les places avant leur nouvelle occupation. Cette différence garde une liste sans collision à chaque remplacement, sans supposer que deux destinataires puissent partager momentanément la même identité.
Ne plus pouvoir ajouter directement n’est pas avoir atteint le maximum
Dans cette branche ajoutant A–trois, Camille commence pourtant une autre préparation : A reçoit un, B deux, D trois et E quatre. C reste sans assiette, cinq libre. Elle ne trouve aucune association à ajouter directement pour C, qui accepte seulement un et deux déjà occupées. Elle présente alors sa liste de quatre comme maximale. Nora accepte seulement le constat local : aucune ligne ne peut être ajoutée en gardant toutes les lignes présentes. La réalisation complète précédente montre que quatre n’est pas le plus grand nombre possible sous ces acceptations nouvelles.
Nora reprend la recherche depuis C. Un conduit à A, qui accepte désormais trois ; trois conduit à D, quatre à E, et cinq est libre. La suite retenue est C, un, A, trois, D, quatre, E, cinq. Elle prépare E à cinq, D à quatre, A à trois, puis C à un. B reste à deux. La nouvelle liste sert les cinq. Le choix précoce A–un avait occupé l’une des deux seules possibilités de B et C avec une personne capable de sortir de ce groupe. Nora retire donc la règle qui faisait de chaque association déjà trouvée une ligne intangible pendant la recherche du plus grand nombre servi.
Cette correction ne prouve pas que le premier choix A–un était interdit. Il était acceptable et pouvait figurer dans une liste partielle. Il empêchait seulement une extension directe de cette liste, tant qu’aucune ligne ne pouvait être remplacée. Nora conserve cette nuance dans le diagnostic : une association permise peut être mal placée pour l’objectif collectif, sans devenir une association refusée par la personne. Le contrôle de groupe et la suite vers cinq ont fourni une réparation concrète. Ils ont changé les lignes nécessaires pour compléter, plutôt que demandé à C d’accepter une assiette que ses données excluent encore.
Une association choisie n’est pas toujours imposée par toutes les listes complètes
Nora conserve les acceptations avec trois ajouté pour A et compare maintenant toutes les listes servant les cinq. B et C acceptent seulement un et deux : ensemble, ils occupent nécessairement ces deux identités. A ne peut alors recevoir ni un ni deux et doit recevoir trois. D ne peut plus recevoir trois et doit recevoir quatre. E reçoit donc cinq. Nora obtient deux listes complètes, qui diffèrent seulement par B–un, C–deux ou B–deux, C–un. Cette vérification n’utilise aucun classement des personnes : elle suit les choix distincts que les deux premières doivent garder et ceux qui restent pour les trois autres.
Nora marque A–trois, D–quatre et E–cinq comme présentes dans chacune des deux listes complètes. Elle ne donne pas ce statut à B–un, même si sa réalisation retenue l’utilise. Supprimer la possibilité B–un laisserait B–deux et C–un, avec les trois autres associations inchangées : les cinq seraient encore servis. Une association inscrite sur la fiche retenue peut donc être remplaçable à l’échelle de toutes les fiches. Nora choisit B–un pour cette remise sans annoncer qu’elle serait nécessaire à la couverture du groupe. Les deux statuts, utilisée et imposée par toutes les réalisations complètes, sont contrôlés séparément.
Elle examine au contraire le retrait de D–quatre des possibilités. B et C doivent toujours occuper un et deux, donc A trois. D n’aurait plus que trois, déjà nécessaire à A. Une liste complète devient impossible. Nora peut garder B–un, C–deux, A–trois et E–quatre, pour quatre personnes, sans D ; elle pourrait choisir une autre liste partielle de quatre. Elle conserve la perte de couverture auprès du retrait de cette association. Elle ne dit pas qu’il suffirait de déplacer D vers sa seconde préférence : aucune préférence n’existe ici et aucune autre possibilité de D n’est encore donnée.
Enfin, Nora retire seulement D–trois et E–quatre, deux associations pourtant autorisées dans la branche complète. Les deux listes de cinq restent réalisables : ni l’une ni l’autre ne les utilisait. Leur retrait ne diminue donc pas le maximum. Camille avait annoncé que toute réduction des possibilités retirerait une personne de la couverture ; Nora corrige cette phrase. Une association peut être inutile aux listes complètes de ces données, remplaçable entre elles, ou nécessaire à chacune. Le nombre de traits effacés n’identifie pas ces situations. Nora conserve les trois contrôles remplis plutôt qu’un compte uniforme des suppressions.
Ajouter une pièce hors du groupe bloqué peut laisser le même déficit
Repartons des acceptations initiales, sans trois pour A. Une sixième identité est ajoutée au stock. Dans une première proposition, D l’accepte en plus de trois et quatre ; les autres listes ne changent pas. Nora souhaite encore servir les cinq personnes. La demande concerne leurs destinations distinctes, sans obligation d’utiliser les six assiettes désormais présentes.
Le stock a grandi, mais A, B et C dépendent toujours de un et deux. Leur déficit de un reste donc entier. Nora maintient le maximum de quatre, qu’elle peut atteindre en donnant un à B, deux à C, six à D et quatre à E. Cinq reste libre, trois aussi. Elle refuse la promesse « avec une assiette supplémentaire, personne ne manque ». La ressource ajoutée a augmenté les possibilités de D, situé hors du groupe qui imposait le manque. Deux identités libres à la fin ne peuvent pas servir le troisième membre de ce groupe si aucune de ses listes ne les contient.
Dans une autre proposition, six est au contraire acceptable pour A et ne s’ajoute pas à la liste de D. Nora choisit A–six, B–un, C–deux, D–trois et E–quatre. Les cinq sont servis, cinq reste libre. Pour A, B et C réunis, les destinations disponibles sont maintenant un, deux et six : le déficit précédent a disparu et cette liste montre effectivement la couverture nouvelle. Nora conserve les deux propositions distinctes. Le nombre six de pièces est commun aux deux, mais l’ajout ne se trouve pas dans les mêmes listes. Le total de stock ne suffisait donc pas à choisir laquelle répondrait à la demande.
Nora envisage encore une ressource différente : une seconde identité du type un, nommée un bis. Elle donne expressément à A, B et C l’acceptation de cette identité supplémentaire, sans retirer celle de un ou deux. D et E gardent leurs listes initiales. Nora peut alors attribuer un à A, un bis à B, deux à C, trois à D et quatre à E. Elle conserve cinq libre. Deux identités du même type fournissent ici deux places parce que la donnée a réellement ajouté une pièce distincte ; imprimer deux fois le nom un sur l’ancienne fiche n’aurait pas créé cette capacité. Le groupe dispose désormais de trois destinations distinctes qu’il accepte.
Cette dernière préparation conserve les types que les trois personnes acceptaient tout en augmentant leur capacité disponible. La préparation donnant six à A avait au contraire ajouté à sa liste une autre identité numérotée. Nora peut retenir l’une ou l’autre, mais transmet les identités exactes auprès de chaque nom. Elle ne réunit pas leurs avantages dans un stock resté à cinq : chacune des deux propositions comporte une pièce supplémentaire effectivement donnée. Ce rappel reste court. Le contrôle développé porte sur l’emplacement de la capacité nouvelle dans les choix du groupe, puis sur une attribution qui montre qu’elle peut réellement combler son manque.
Un contrôle par les extrémités peut borner toutes les paires
Nora cherche enfin un second certificat du maximum de quatre dans les acceptations initiales. Elle dessine un trait pour chaque association permise, reliant un nom à un numéro. Elle veut sélectionner des repères tels que chaque trait possède au moins une extrémité sélectionnée. Un repère peut être un nom de personne ou une identité d’assiette ; cela ne les rend pas interchangeables pour le service. Cette sélection doit couvrir les associations du dessin, alors que la liste à remettre attribuera les assiettes à leurs destinataires.
Elle choisit les numéros un et deux, puis les noms D et E. Tous les traits de A, B et C touchent un ou deux ; tous ceux de D et E touchent le nom sélectionné correspondant. Quatre repères suffisent donc à couvrir chaque association permise. Camille propose à la place les numéros un, deux, trois et quatre. Nora refuse ce certificat : le trait E–cinq ne touche aucun de ces quatre repères. Ceux-ci pourraient correspondre aux assiettes d’une réalisation de quatre, mais leur liste n’a pas couvert toutes les possibilités à contrôler. Nora conserve la sélection mêlant deux numéros et deux noms, dont chaque trait a réellement rencontré une extrémité.
Cette sélection borne le nombre de paires attribuables. Chaque paire retenue doit toucher au moins un repère sélectionné, puisque toutes les associations sont couvertes. Deux paires d’une attribution ne peuvent pas utiliser le même nom ni le même numéro. Elles ne peuvent donc pas se partager ce repère pour expliquer leur présence. Nora associe ainsi un repère distinct à chaque paire retenue ; avec quatre repères disponibles, il ne peut pas y avoir cinq paires disjointes. Ce contrôle porte sur toutes les attributions possibles, pas seulement celle où A manque. Il retrouve le maximum de quatre sans avoir à choisir d’abord lequel des trois premiers noms restera dehors.
Nora vérifie également qu’aucune sélection de trois repères ne couvrirait tous les traits. Sa réalisation B–un, C–deux, D–trois, E–quatre contient déjà quatre traits sans extrémité commune. Couvrir ces quatre traits demande au moins quatre repères distincts, même si l’on peut choisir pour chacun son nom ou son numéro. La sélection trouvée à quatre atteint donc elle aussi un minimum. Nora remet ensemble une attribution de quatre et une couverture des associations à quatre : l’une atteint le nombre servi, l’autre empêche de le dépasser. Après l’ajout A–trois, l’ancienne couverture ne suffit plus, car ce trait nouveau ne touche ni un, ni deux, ni D, ni E. Elle ne doit pas être conservée comme borne dans cette autre branche.
Nora remet ainsi les listes et leurs limites avec le même objet de contrôle : chaque personne reçoit au plus une identité, aucune identité n’est partagée et chaque association appartient aux acceptations du cas. Un groupe peut expliquer une couverture impossible ; une suite vers une place libre peut compléter une préparation bloquée ; les listes complètes peuvent imposer certaines associations sans imposer toutes celles du choix retenu. Les assiettes fictives ne donnent aucune préférence ou performance réelle. Elles rendent vérifiables les décisions de cette table de papier, sans demander au seul nombre de pièces de promettre ce que leurs destinations ne permettent pas.