Dans la maison de Jeanne, six petites séances doivent tenir sur une même matinée. A prépare les étiquettes, B reçoit les objets apportés, C compare deux inventaires, D organise les photographies, E relit les légendes et H réunit les décisions finales. Ce sont les noms des séances, pas les initiales de six personnes. Deux séances peuvent commencer ensemble si elles disposent de personnes distinctes et de pièces distinctes. Jeanne a prévu plusieurs pièces ; elle ne cherche donc pas à placer une seule séance à la fois. Ce qui bloque une paire est la présence nécessaire d'une même personne aux deux séances, au même moment.
Jeanne trace les incompatibilités que les personnes lui ont effectivement annoncées. A ne peut pas coïncider avec B ni avec E. B ne peut pas coïncider avec C. C ne peut pas coïncider avec D. D ne peut pas coïncider avec E. Enfin H ne peut coïncider avec aucune des cinq autres séances. La feuille contient exactement dix traits : AB, BC, CD, DE, EA, puis HA, HB, HC, HD et HE. Un trait interdit un horaire commun à ses deux extrémités. Une paire sans trait n'est pas automatiquement installée dans la même pièce ; elle est seulement libre de partager un créneau si les pièces et les autres personnes prévues le permettent. Dans ce cas inventé, Jeanne a vérifié cette capacité pour les paires qu'elle utilisera.
Filofax présente des agendas. Jeanne y note ses heures ; les dix conflits sont créés pour ce cas.
AT-A-GLANCE présente des calendriers. Aucune capacité de salle n’est reprise de cette page.
Moleskine présente des planificateurs hebdomadaires. Aucun fonctionnement de produit n’entre dans la preuve.
La première feuille à quatre heures
Malik, qui tient le tableau, commence par placer A et C au premier créneau. Aucun trait AC ne les relie. Il place B et D au deuxième ; BD n'est pas non plus un conflit. E prend le troisième, car elle touche D et A, ainsi que H. H prend le quatrième. Le tableau se lit donc 1 : A,C ; 2 : B,D ; 3 : E ; 4 : H. Il ne cache aucune séance. Chaque trait de la liste relie deux lignes différentes : AB va de 1 à 2, BC de 2 à 1, CD de 1 à 2, DE de 2 à 3, EA de 3 à 1 ; les cinq traits issus de H vont de 4 à une ligne comprise entre 1 et 3.
Jeanne refuse pourtant de valider une heure seulement parce que les dix traits connus sont respectés. Elle vérifie les deux paires qui partagent vraiment une ligne : A avec C au premier créneau, B avec D au deuxième. Leurs responsables déclarés sont distincts et deux pièces sont disponibles à chacune de ces deux heures. Sans cette vérification de capacité, l'absence de trait serait un silence, pas une réservation. Le quatrième créneau de H est une place dans l'emploi du temps, non la preuve que H doit être seule dans toute maison possible. Malik note la vérification en face des deux paires au lieu de la transformer en règle universelle sur les agendas.
La directrice demande pourquoi trois heures ne suffiraient pas. Malik pourrait exhiber l'échec de plusieurs coloriages essayés, mais un essai raté ne ferme pas toutes les possibilités. Il isole les cinq premières séances. A, B, C, D et E forment un anneau de conflits : A touche B, B touche C, C touche D, D touche E et E revient toucher A. Si l'on essaie seulement deux heures, choisir A à la première force B à la seconde, C à la première, D à la seconde et E à la première. Le dernier trait EA interdit alors précisément l'heure donnée à E. Inverser les deux heures ne change rien. Cet anneau de longueur cinq exige au moins une troisième heure.
La troisième heure ne peut pas accueillir H dans le tableau initial. Quel que soit le partage des cinq séances sur trois heures, chacune de ces trois heures est occupée par au moins une séance de l'anneau : l'anneau ne peut pas se contenter de deux. H est incompatible avec chacune des cinq séances. La mettre sur l'une des trois heures lui donnerait donc au moins une voisine interdite à la même heure. Pour limiter le total à trois, on ne peut ni laisser une heure vide dans l'anneau ni loger H dans une heure occupée. Il faut une quatrième heure. Le tableau de Malik en fournit une, de sorte que quatre est à la fois une borne inférieure et une réalisation, sous les contraintes effectivement écrites.
Malik veut savoir si sa feuille à quatre lignes est la seule. En ignorant le nom des heures, il peut choisir laquelle des cinq séances de l'anneau occupe seule une ligne : A, B, C, D ou E. Les quatre autres forment alors un chemin. En partant d'une extrémité de ce chemin, leurs deux lignes alternent ; H garde la quatrième pour elle seule. Si E est la séance isolée, on obtient précisément les groupes A,C puis B,D puis E puis H. Si A est isolée, les deux groupes deviennent B,D et C,E, avec A et H séparées. Ce ne sont pas cinq nombres minimaux différents, mais cinq répartitions de présences à quatre heures que Jeanne peut soumettre aux personnes concernées.
Pour vérifier que cette liste n'oublie pas un partage, Malik prend une séance isolée de l'anneau et suit les quatre autres dans leur ordre circulaire. Les deux extrémités du chemin ne peuvent partager la couleur de leurs voisines immédiates ; alterner les deux autres couleurs satisfait tous les traits restants. Une configuration à trois couleurs de l'anneau doit avoir une couleur portée par une seule séance : cinq positions distribuées sur trois couleurs ne peuvent faire trois groupes d'au moins deux. Le sommet isolé choisi détermine alors les deux paires alternées. Il reste exactement les cinq choix de ce sommet, sous les seules contraintes de conflits. Jeanne ne transforme pas ce décompte abstrait en cinq réservations automatiques : chaque paire réellement retenue doit encore passer le contrôle de pièces et de personnes.
Jeanne relit cette démonstration dans l'autre sens. Le nombre quatre ne vient pas d'une préférence pour les longues matinées ou d'une formule inscrite sur le planificateur. Il vient de deux obstacles précis : le retour de E vers A empêche l'alternance de deux heures, et les cinq liens de H empêchent de partager la troisième. Si l'un de ces obstacles cesse réellement d'exister, un tableau de trois heures peut devenir possible. Effacer un trait pour embellir la feuille, alors que la personne reste attendue aux deux séances, ne serait pas une correction du programme ; ce serait une promesse fausse faite aux participants.
Une question d'effectifs, et non de crayon
À la réunion suivante, Jeanne vérifie le trait HE. La même spécialiste était portée comme présence indispensable à la relecture E et à la décision H. Elle précise désormais que sa partie de H a été transmise avant la matinée : elle garde son rôle à E, tandis qu'une autre personne déjà affectée à H présente ce point. La spécialiste n'a plus à assister à H. Les deux séances restent entières ; leurs objectifs, leurs autres présences et leurs pièces ne changent pas. La seule incompatibilité retirée est HE. Jeanne écrit la décision et son motif avant que Malik ne touche au tableau. Si la transmission n'était pas effective, HE devrait rester.
Malik reprend alors exactement A,C à l'heure 1 et B,D à l'heure 2. Il met E et H ensemble à l'heure 3. Les deux n'ont plus de personne requise commune après la transmission, et deux pièces sont prévues à cette heure. Il contrôle les neuf traits encore en vigueur : AB, BC, CD, DE, EA séparent toujours les heures de l'anneau ; HA et HC vont de 3 à 1, HB et HD de 3 à 2. Aucun trait HE ne subsiste. Cette dernière phrase ne signifie pas que H pourrait partager n'importe quelle heure : ses quatre autres liens sont restés. Le nouveau tableau est 1 : A,C ; 2 : B,D ; 3 : E,H.
La troisième heure n'est pas facultative dans ce premier correctif. L'anneau AB, BC, CD, DE, EA est intact et demande toujours trois heures par l'alternance impossible. Après la suppression effective de HE, H peut utiliser l'heure de E, ce qui atteint cette borne. Même si quelqu'un proposait de démarrer H à la première heure au motif que « son conflit a été levé », HA et HC l'interdiraient encore. À la deuxième, HB et HD l'interdiraient. La position de H à la troisième n'est pas un artifice de numérotation ; elle provient de la seule place libérée dans ce tableau.
Ce correctif impose même les groupes du tableau à trois lignes, à permutation des heures près. H ne peut partager qu'avec E, car HA, HB, HC et HD subsistent. Elle ne peut être seule si les trois heures sont toutes utilisées par l'anneau. E et H occupent donc nécessairement la même ligne. En ôtant E du cercle pour examiner les quatre autres, A-B-C-D est un chemin dont les couleurs doivent alterner entre les deux lignes disponibles : A avec C, B avec D. Une proposition de mettre A avec D après le retrait de HE paraît permise par leur absence de trait, mais elle laisserait B et C sans répartition compatible sur les deux autres lignes. L'absence d'un conflit direct entre deux séances ne suffit pas à garantir qu'elles puissent être placées ensemble dans une solution minimale complète.
Jeanne soumet un scénario différent, sans cumuler les deux corrections. Supposons que la transmission concernant HE n'ait jamais eu lieu : H reste incompatible avec toutes les séances. En revanche, les responsables qui devaient participer ensemble à A et E auraient réellement terminé leur échange la veille ; il n'y aurait plus de présence commune entre A et E. Cette vérification retirerait EA, pas HE. Il ne s'agit pas de déplacer la même spécialiste entre E et H. Ce sont deux causes distinctes, et Jeanne garde deux versions séparées de la feuille pour éviter qu'une preuve attachée à l'une serve abusivement à l'autre.
Sans EA, les cinq séances de l'anneau devenu chemin peuvent alterner : A,C,E à l'heure 1, B,D à l'heure 2. Malik vérifie les quatre liens qui restent dans ce chemin : AB, BC, CD, DE passent tous d'une heure à l'autre. E partage la première heure avec A et C parce que le lien EA a été retiré après vérification ; elle n'a jamais eu de lien EC. Les trois pièces et les responsables distincts requis pour ce groupe sont confirmés pour cette variante. H reste seule à l'heure 3, puisque chacun de ses cinq liens demeure. Le tableau complet est donc 1 : A,C,E ; 2 : B,D ; 3 : H.
Dans ce second scénario, H empêche même une solution à deux heures. Puisqu'elle touche toutes les autres séances, une heure où H se trouve ne peut contenir aucune des cinq. Les cinq ne peuvent pas toutes être mises dans l'unique heure restante : AB, par exemple, resterait un conflit. Deux heures sont donc impossibles, et le tableau à trois est minimal. La justification n'est pas celle du premier correctif. Là, l'anneau imposait trois et H partageait E ; ici, l'anneau ne demande plus que deux, mais H impose une heure séparée. Les deux feuilles ont le même nombre de lignes sans décrire les mêmes présences.
Ici aussi, le partage minimal est imposé par les traits restants. H possède sa ligne à elle. Les cinq autres doivent tenir dans les deux lignes qui restent, et le chemin A-B-C-D-E force A, C, E à alterner face à B, D. Si Malik voulait garder E seule comme sur la première feuille, il emploierait trois lignes pour le chemin et une quatrième pour H ; il perdrait l'heure qu'il prétend économiser. L'enjeu pratique du retrait de EA est donc de vérifier une capacité triple à la première heure, pas seulement d'effacer un trait entre deux noms. Si la troisième pièce promise manque, la preuve des conflits reste correcte mais ce programme à trois heures cesse d'être réalisable dans la maison.
La différence entre les deux feuilles devient décisive si Jeanne ne dispose finalement que de deux pièces à chaque heure. Le retrait de HE garde trois groupes de taille deux : A,C ; B,D ; E,H. Ses trois heures restent réalisables avec ces deux pièces et les présences déjà vérifiées. Le retrait de EA, en revanche, exige dans sa solution minimale que A,C,E soient simultanées ; trois séances réclament alors trois pièces. Deux pièces ne peuvent pas recevoir ce groupe. On pourrait répartir le chemin sur trois heures de capacité deux, puis réserver une quatrième heure à H, mais cela ne sauverait plus l'objectif de trois créneaux. Ainsi une correction de conflit qui abaisse le minimum abstrait à trois ne suffit pas si une contrainte de capacité distincte ramène le minimum praticable à quatre.
Jeanne peut vérifier la dernière affirmation sans essayer tous les horaires. Avec EA retiré et H toujours incompatible avec chacune des cinq autres, H occupe seule l'une des trois heures que l'on voudrait conserver. Il ne reste que deux heures pour A, B, C, D et E. Sous la limite de deux pièces, ces deux heures ne portent au maximum que quatre séances. Or il en reste cinq. La contradiction vient ici du compte de places, même avant de consulter les quatre conflits du chemin. Si une troisième pièce est réellement confirmée, la feuille A,C,E ; B,D ; H redevient une réalisation de trois heures. La même correction EA a donc deux conséquences opérationnelles différentes selon une donnée que Jeanne doit obtenir, et non deviner.
Malik remarque que la suppression d'un seul trait suffit dans chacun de ces deux scénarios, mais que zéro suppression ne pouvait pas suffire : le tableau initial demandait quatre. Il n'en déduit pas que n'importe quel trait serait gratuitement supprimable. Un conflit entre personnes a une cause qu'il faut modifier ou vérifier. Il n'en déduit pas non plus que les deux suppressions puissent être combinées sans nouvel accord : la feuille HE et la feuille EA sont des alternatives. Le mot « minimal » désigne ici le nombre de corrections de conflit nécessaires pour rendre trois heures mathématiquement possibles dans les conditions posées. Il ne mesure ni la difficulté humaine de chacune ni le coût d'une transmission réelle.
Les fausses corrections que la feuille révèle
Une assistante propose simplement de renommer l'heure 4 en « heure 3 bis ». H continuerait à se tenir après E et la matinée comporterait toujours quatre périodes distinctes. Une autre propose de mettre H dans la première heure en ajoutant une seconde pièce. Dans la feuille initiale, une seconde pièce ne retire pas HA ni HC : les personnes requises à A et C seraient toujours requises à H. La capacité de pièce et la disponibilité des personnes sont deux contraintes différentes. Jeanne accepterait une salle supplémentaire pour rendre possible un partage déjà permis, pas pour nier un trait de présence.
Malik essaie aussi de déplacer E à l'heure 2 du tableau initial afin de libérer la troisième pour H. Le trait DE fait échouer E avec D, et H ne peut pas rejoindre A,C ni B,D de toute façon. Déplacer une séance sans effacer sa dépendance reporte le problème sur une autre ligne. Il inscrit les deux conflits en face de la tentative au lieu de déclarer vaguement que la réorganisation « ne marche pas ». Cette trace aide Jeanne à distinguer une permutation sans effet d'une modification de la situation : le retrait vérifié de HE change un lien ; un simple déplacement de E ne le change pas.
La directrice demande si annuler H serait plus rapide. Oui, cinq séances sans H tiennent dans les trois heures de l'anneau initial, mais ce n'est pas la même commande : la décision finale n'aurait plus lieu. Annuler E aurait également changé le dossier plutôt que son horaire. Jeanne maintient les six séances dans chaque feuille qu'elle présente. Son économie d'une heure est recevable seulement si les six résultats attendus restent produits. Cette condition empêche de célébrer comme une « optimisation » un tableau plus court dont une ligne importante a disparu.
Elle distingue enfin la matinée fictive d'un rendez-vous réel. Si une règle extérieure imposait une unique pièce ou une personne commune à toutes les séances, chaque paire deviendrait incompatible et six heures seraient nécessaires ; ni le tableau à quatre ni les variantes à trois ne seraient des réservations valides. À l'inverse, l'existence de plusieurs pièces ne prouve pas que toutes les paires sont compatibles. Le modèle des dix traits est utilisable parce qu'il décrit les présences exigées et parce que les partages annoncés ont été vérifiés pour ce cas. Il faut rouvrir la feuille dès qu'une présence ou une capacité change effectivement.
Malik conserve la feuille initiale à quatre lignes, puis les deux feuilles conditionnelles à trois lignes, chacune avec sa décision de personnel en tête. Jeanne choisit la première variante uniquement après confirmation de la transmission qui retire HE. E et H commenceront ensemble à la troisième heure dans deux pièces distinctes ; A et C partageront la première, B et D la seconde. Si la confirmation est retirée, le programme revient à quatre lignes plutôt que de conserver en public un horaire invalide. La petite matinée tient désormais dans trois heures, mais c'est une information vérifiée sur un lien humain, non l'élégance d'un tableau, qui a libéré l'heure.
Le second responsable attendu n'arrive pas
Au moment d'exécuter cette première variante, Jeanne reçoit une information qui n'était pas sur la feuille des dix conflits : les séances B et D devaient être suivies chacune par un responsable différent, mais une seule personne arrive pour les deux. Elle peut assister à B puis à D, pas aux deux à la même heure. Le trait BD s'ajoute aux incompatibilités de cette matinée ; HE reste bien retiré, et aucune séance n'est annulée. Jeanne inscrit le nom du responsable sur B et D avant de changer l'horaire. La feuille à trois heures A,C ; B,D ; E,H ne peut plus être remise telle quelle : sa deuxième ligne exige deux présences simultanées de cette même personne.
Malik ne se contente pas de déplacer D vers une ligne qui paraît moins pleine. Avec HE retiré, H reste incompatible avec A, B, C et D : pour tenir en trois heures, H doit partager celle de E. Les quatre autres séances A, B, C et D n'auraient alors que deux heures. Leurs conflits AB, BC et CD imposent l'alternance A,C face à B,D ; le nouveau BD interdit justement la seconde paire. La contradiction tient même si trois pièces sont disponibles. Mettre D auprès de E,H échoue à cause de HD et DE, et mettre B auprès de E,H échoue à cause de HB. Le quatrième créneau n'est pas obtenu en renommant une ligne : aucune affectation à trois ne respecte maintenant le responsable effectivement présent.
Jeanne fait la correction sur une nouvelle feuille d'exécution : heure 1 A,C ; heure 2 B ; heure 3 E,H ; heure 4 D. Elle vérifie AB et BC entre les deux premières heures, CD entre la première et la quatrième, DE entre la troisième et la quatrième, EA entre la première et la troisième. H ne partage qu'avec E ; B et D ont des heures différentes. Le responsable assiste réellement à B à la deuxième heure, reçoit sa sortie, puis à D à la quatrième. Les quatre lignes conservent les six séances, et la quatrième est nécessaire après l'arrivée d'une personne au lieu des deux annoncées. Jeanne retire le reçu de trois heures de cette réalisation, sans retirer la preuve de trois heures attachée à la situation antérieure.
Une remplaçante confirme plus tard sa présence pour une autre matinée ayant exactement les mêmes séances et la transmission HE déjà validée. Jeanne lui attribue D, garde le premier responsable sur B et vérifie que chacun dispose de sa pièce au même deuxième créneau. Le trait BD n'a alors plus de cause dans cette autre réalisation : A,C ; B,D ; E,H redevient une feuille exécutable en trois heures. Elle ne raconte pas que la remplaçante est arrivée dans la matinée où une seule personne a assuré B puis D. Les deux reçus portent des présences effectives différentes ; le nombre de lignes dépend de cette présence vérifiée, et pas seulement du dessin d'incompatibilités que Malik avait d'abord résolu.