Dans une maison fictive, Jeanne dessine sept colonnes contiguës pour préparer une affiche rectangulaire sur une feuille. Chaque colonne a une largeur abstraite de un et possède un plafond au-dessus duquel rien ne doit être dessiné. L'affiche doit occuper des colonnes consécutives, avec une seule hauteur commune sur toute sa largeur. Camille propose de choisir les deux colonnes les plus hautes, mais Nora demande d'abord où elles se trouvent. Deux hauteurs élevées séparées par une colonne basse ne forment pas automatiquement un seul rectangle haut.
Le profil, de gauche à droite, est deux, un, quatre, cinq, un, trois, trois. Ce sont les hauteurs d'un dessin, sans unité matérielle. Une affiche de la colonne i à la colonne j prend la hauteur minimale rencontrée dans cet intervalle, puis son aire vaut cette hauteur multipliée par le nombre de colonnes. Des pages officielles de Bisley, Montana et USM attestent seulement des catégories de mobilier ou de rangement. Aucune dimension, solidité, capacité ni méthode de ces entreprises n'est transférée à la feuille de Jeanne.
Jeanne inscrit les sept valeurs avec leurs positions : la colonne un vaut deux, la deux vaut un, les trois et quatre valent quatre et cinq, la cinq vaut un, les six et sept valent trois chacune. Cette liste permet de reconstruire la feuille sans croquis. Un rectangle peut être moins haut que le plafond d'une colonne, mais ne peut pas dépasser ce plafond. Si la hauteur choisie est exactement le minimum d'un intervalle, augmenter cette hauteur violerait au moins une colonne ; la diminuer sans changer la largeur ne ferait que réduire son aire. Il suffit donc d'examiner le minimum propre à chaque intervalle.
Camille voit la colonne quatre, haute de cinq, et annonce une affiche d'aire cinq. Jeanne ne la rejette pas comme impossible : une seule colonne de largeur un et de hauteur cinq convient. Elle refuse seulement de la proclamer maximale. Les colonnes trois et quatre sont voisines et toutes deux atteignent quatre ; une affiche qui les couvre à hauteur quatre a largeur deux et aire huit. La cinquième colonne, haute de un, interdit de prolonger ce même rectangle d'une colonne vers la droite à hauteur quatre. Ce témoin d'aire huit renverse déjà le choix initial.
Pour savoir si huit est vraiment le maximum, Nora ne se contente pas de tester quelques rectangles agréables à l'œil. Elle prend chaque barre à son tour comme hauteur limitante et cherche jusqu'où elle peut étendre un intervalle avant de rencontrer une barre strictement plus basse. Une barre plus haute ne gêne pas le rectangle à cette hauteur. Une barre égale peut demeurer dans le même intervalle. Chaque rectangle possible possède au moins une barre qui réalise sa hauteur minimale ; l'extension maximale autour de cette barre ne donne donc jamais une aire inférieure à celle du rectangle de départ.
La barre de hauteur deux en première position rencontre immédiatement la hauteur un en deuxième. À hauteur deux, elle ne peut couvrir qu'une colonne : aire deux. La barre de hauteur un en deuxième position peut, elle, s'étendre de la première à la septième, puisque toutes les autres atteignent au moins un. Elle donne un rectangle de largeur sept et d'aire sept. Le même raisonnement vaut pour la barre de hauteur un en cinquième position. Ces deux barres basses n'imposent pas deux affiches différentes : elles certifient la même possibilité à hauteur un sur toute la largeur.
La troisième barre, haute de quatre, rencontre la hauteur un en deuxième position à gauche et en cinquième à droite. Entre ces deux limites, seules les positions trois et quatre restent possibles à hauteur quatre. La largeur maximale est deux, d'où l'aire huit déjà trouvée. La quatrième barre, haute de cinq, rencontre à gauche la barre de quatre, qui est plus basse qu'elle, puis à droite celle de un. À hauteur cinq, elle reste donc seule et donne cinq. L'existence d'une hauteur cinq ne permet pas de compter la voisine de hauteur quatre comme si elle avait grandi.
Les deux dernières barres sont chacune de hauteur trois. Vers la gauche, la cinquième colonne de hauteur un arrête leur prolongement ; vers la droite, la feuille s'arrête après la septième. À hauteur trois, elles couvrent ensemble les positions six et sept : largeur deux, aire six. Traiter l'une de ces deux barres comme limite n'exige pas d'exclure l'autre, puisqu'une hauteur égale respecte le même plafond. Nora obtient alors les seules bornes pertinentes par hauteur limitante : deux, sept, huit, cinq, sept et six selon la position, avec six encore pour la dernière barre. Huit les dépasse toutes.
La démonstration explique pourquoi l'affiche retenue va exactement des colonnes trois à quatre et atteint quatre de hauteur. Une proposition qui omettrait la quatrième perdrait la largeur donnant huit. Une proposition qui ajouterait la deuxième ou la cinquième tomberait à hauteur un et ne récupérerait pas ce manque par sa largeur. Nora peut indiquer un rectangle effectivement réalisable et une borne pour toute autre possibilité. Elle n'affirme ni que la feuille porte déjà une affiche ni que les valeurs décrivent un meuble réel ; elle remet un choix dans le modèle annoncé.
Camille suggère de demander une largeur minimale de trois pour rendre l'affiche plus lisible dans le dessin. Cette demande nouvelle élimine l'ancien optimum de largeur deux. Chaque suite d'au moins trois colonnes touche la deuxième ou la cinquième barre basse : les zones entre ces deux positions sont trop courtes pour accueillir trois colonnes. Sa hauteur ne peut donc dépasser un. Parmi ces suites, prendre les sept colonnes donne l'aire sept, supérieure aux largeurs trois à six à la même hauteur. Nora remet un autre choix pour cette commande, plutôt que déclarer l'aire huit encore admissible sous le nouveau titre.
Si la largeur devait être exactement trois, et non au moins trois, le rectangle couvrant toute la feuille serait à son tour interdit. Chaque groupe de trois colonnes contient encore une barre de hauteur un ; son aire vaut trois. Jeanne conserve cette différence entre « exactement » et « au moins » dans la fiche. Une largeur au moins trois donnait sept sur toute la feuille ; une largeur exactement trois donne trois sur n'importe lequel des cinq intervalles de trois. Les deux critères portent sur le même profil, mais ils ne sélectionnent pas la même permission.
Une correction arrive sur le profil original : la quatrième hauteur avait été écrite cinq et doit devenir deux. Toutes les autres colonnes gardent leurs anciennes valeurs. L'affiche trois à quatre, autrefois de hauteur quatre et d'aire huit, devient une affiche de hauteur deux et d'aire quatre. Jeanne ne reprend pas le maximum huit depuis l'ancienne fiche par inertie. La feuille possède encore les deux colonnes finales de hauteur trois, aire six, et le rectangle de toute la largeur à hauteur un, aire sept. Ce dernier devient le meilleur des candidats déjà identifiés.
Pour achever le contrôle après cette baisse, Nora regarde les intervalles qui touchent la quatrième colonne. Ceux qui ne la touchent pas ont exactement les mêmes minima et les mêmes aires qu'avant. Un intervalle contenant maintenant la quatrième à hauteur deux ne peut pas franchir la deuxième ou la cinquième barre de hauteur un s'il veut conserver deux. Entre ces limites, il couvre au plus les colonnes trois et quatre, donc aire quatre. S'il franchit une barre de un, sa hauteur tombe à un et sa largeur ne dépasse sept. Aucun rectangle modifié ne dépasse sept ; le maximum du profil corrigé est bien sept, sur toute la largeur.
Ce contrôle local n'affirme pas qu'une baisse de barre réduit toujours l'optimum. Il dit ce qu'il faut recalculer pour cette baisse précise : les rectangles qui contiennent la position corrigée, puis les anciens concurrents inchangés. Si la colonne quatre n'avait jamais appartenu à un rectangle optimal, le meilleur pourrait rester identique. Ici elle appartenait au témoin d'aire huit, et les nouveaux intervalles passant par elle sont trop faibles pour le remplacer. Le lien entre la correction reçue et la nouvelle décision est ainsi explicite.
Jeanne ouvre une autre branche depuis le profil initial, sans cumuler la baisse précédente. Cette fois, la cinquième hauteur passe de un à deux ; les six autres restent deux, un, quatre, cinq, trois et trois. La suite des colonnes trois à sept possède désormais les hauteurs quatre, cinq, deux, trois, trois. Son minimum est deux, sa largeur cinq et son aire dix. Ce candidat n'existait pas à cette hauteur dans l'ancien profil, puisque la cinquième colonne de hauteur un coupait son passage. La correction d'une seule valeur ouvre une bande plus large au lieu de seulement grandir une barre isolée.
Nora vérifie que dix est bien le nouveau maximum. À hauteur supérieure à deux, la cinquième colonne reste un obstacle ; les colonnes trois et quatre ne donnent toujours que huit, et les six et sept donnent six. À hauteur deux, la deuxième colonne de hauteur un bloque la gauche, mais la suite trois à sept offre la largeur cinq donnant dix. À hauteur un, les sept colonnes donnent sept. Aucun autre niveau permis n'améliore ces trois bornes. Jeanne peut remettre l'affiche trois à sept, hauteur deux, avec une preuve qui ne dépend pas d'une impression de surface plus grande.
Camille pensait que hausser une barre de un à deux ajouterait simplement une unité d'aire, puisque la barre n'a gagné qu'un cran. L'aire maximale passe pourtant de huit à dix. Le gain n'est pas l'aire de la seule colonne modifiée : cette colonne sert de passage entre les hautes positions trois et quatre et les positions six et sept. Leur nouvelle largeur commune est cinq. L'opération inverse, ramener la cinquième à un, détruirait ce candidat sans retirer les autres hauteurs. Nora annote la cause de l'augmentation plutôt qu'une simple différence numérique de deux.
Une troisième branche revient encore au profil initial. La deuxième hauteur monte de un à trois. Les positions deux, trois et quatre ont alors pour hauteurs trois, quatre et cinq ; une affiche commune à hauteur trois couvre trois colonnes et vaut neuf. La première colonne, haute de deux, interdit d'étendre ce rectangle vers la gauche à hauteur trois ; la cinquième, haute de un, l'interdit vers la droite. Le meilleur rectangle se déplace donc d'un départ en troisième colonne à un départ en deuxième, au lieu de s'élargir dans la direction utilisée par la correction de la cinquième.
Le contrôle des concurrents confirme neuf. Le rectangle trois à quatre conserve son aire huit. Un rectangle partant de la première et allant jusqu'à la quatrième reste limité à deux, donnant au plus huit sur quatre colonnes. Ceux qui traversent la cinquième restent limités à un, donnant au plus sept sur toute la feuille. Les deux dernières colonnes valent toujours six à hauteur trois. Nora retient donc neuf pour cette branche, et non dix : les deux hausses d'une seule barre basse n'ont pas été appliquées au même endroit ni dans la même version. Leurs intervalles nouveaux ne sont pas interchangeables.
Jeanne demande ensuite si l'on peut permuter deux hauteurs sans changer la réponse. Elle reprend une fois encore la liste originale et échange seulement les valeurs des colonnes quatre et cinq. La nouvelle suite est deux, un, quatre, un, cinq, trois, trois. Les mêmes sept hauteurs sont présentes, leur somme n'a pas changé, mais la barre de un s'intercale désormais entre celle de quatre et le groupe de cinq, trois, trois. Le vieux rectangle trois à quatre ne possède plus hauteur quatre : il tombe à un. La simple identité de l'inventaire ne préserve pas les voisinages utiles.
Dans cette version permutée, les colonnes cinq à sept ont pour hauteurs cinq, trois, trois. Elles portent un rectangle de hauteur trois, largeur trois, aire neuf. La troisième colonne de hauteur quatre reste seule de son côté de la nouvelle barre basse ; elle n'offre que quatre à cette hauteur. La largeur entière à hauteur un donne sept ; aucun groupe situé autour de la première barre basse n'atteint neuf. Nora choisit donc la bande cinq à sept. Une permutation adjacente a relevé le maximum de huit à neuf, sans ajouter de hauteur à la feuille.
Camille propose alors de trier toutes les colonnes par hauteur croissante pour obtenir le plus grand rectangle possible avec le même inventaire. Jeanne calcule la suite un, un, deux, trois, trois, quatre, cinq. Ses quatre dernières positions atteignent au moins trois ; elles donnent une largeur quatre et une aire douze. Les cinq dernières à hauteur deux donnent dix ; les deux dernières à hauteur quatre donnent huit ; toute la largeur à hauteur un donne sept. Pour cette suite triée, douze est le maximum. Elle peut comparer douze à huit, mais ne remplace pas la feuille originale par la suite triée sans noter que six positions ont changé.
Le tri apporte un exemple frappant, pas une permission de réordonner le projet d'autrui. La demande initiale portait sur sept colonnes dans un ordre déjà remis. Si l'ordre est fixé, douze ne répond pas à la question, même si le multiensemble des hauteurs est le même. Si l'ordre est expressément libre, le tri offre une construction vérifiable, avec son rectangle sur les quatre dernières colonnes. Jeanne conserve les deux états avec leur règle propre. Dire seulement « les hauteurs permettent douze » aurait caché la condition supplémentaire de permutation complète.
Nora rédige maintenant une procédure pour ne plus dépendre d'une recherche improvisée. Pour chaque colonne, elle note la première hauteur strictement plus basse rencontrée en allant vers la gauche et vers la droite. Entre ces deux limites, toutes les barres atteignent au moins sa hauteur ; le produit de cette hauteur par le nombre de positions intérieures est le plus grand rectangle dont cette colonne est limitante. Si deux barres sont égales, aucune n'arrête l'autre : toutes deux peuvent certifier le même intervalle. Elle garde le produit maximal parmi ces candidats avec ses bornes de colonnes.
Cette procédure couvre tous les intervalles du dessin. Supposons qu'un rectangle admissible aille de i à j et atteigne la hauteur m, minimum des hauteurs sur ces positions. Choisissons une colonne de cet intervalle dont la hauteur vaut m. Les premières barres strictement plus basses situées de part et d'autre ne peuvent se trouver à l'intérieur de i à j, sinon le minimum y serait inférieur à m. L'intervalle étendu autour de la colonne choisie contient donc le rectangle examiné et conserve la hauteur m. Son aire est au moins aussi grande. En prenant le meilleur des extensions, Nora ne peut manquer un optimum.
Pour cette feuille de sept colonnes, elle a également contrôlé directement les vingt-huit intervalles contigus possibles : sept choix de départ, puis un nombre décroissant de fins, soit sept plus six jusqu'à un. Elle conserve cette énumération comme preuve de contrôle du cas, pas comme description d'un travail fait par une personne sur un meuble. La procédure par premières barres plus basses donne une justification générale plus courte ; l'énumération permet de repérer une erreur éventuelle dans les chiffres particuliers huit, sept, dix ou neuf des versions corrigées.
Camille souhaite inscrire la somme des hauteurs, dix-neuf, à côté du maximum huit. Jeanne accepte la somme comme un contrôle du profil de départ, mais pas comme un critère de choix de l'affiche. La version où les quatrième et cinquième hauteurs sont échangées garde dix-neuf et donne neuf ; la version triée garde dix-neuf et donne douze. La somme mesure toutes les colonnes à leurs hauteurs différentes. Un seul rectangle doit prendre une hauteur uniforme sur des colonnes consécutives. Confondre ces deux opérations ferait choisir une affiche dont une partie franchit son plafond.
Un autre contrôle met la largeur au premier plan. Le maximum huit utilisait seulement deux colonnes ; le meilleur sous une largeur d'au moins trois utilisait les sept colonnes à hauteur un. La version où la cinquième hauteur devient deux offre au contraire cinq colonnes à hauteur deux, aire dix, et satisfait aussi la largeur minimale. Jeanne n'infère donc pas de l'ancien résultat sept que toute demande large doit rester basse. Le profil corrigé change les intervalles admissibles au niveau deux ; elle refait la décision avec la nouvelle donnée plutôt que transporter un ancien chiffre.
Deux affiches avec une colonne laissée blanche
Une autre commande conserve exactement les sept hauteurs d'origine, sans correction ni permutation. Elle demande deux affiches distinctes, l'une entièrement à gauche et l'autre entièrement à droite d'une colonne laissée blanche pour une note. Chacune doit occuper au moins une colonne ; aucune ne peut franchir cette réserve ou emprunter une colonne à l'autre. Camille ne peut plus remettre le seul rectangle d'aire huit comme réponse à la commande entière. Elle doit choisir la place de la note et deux intervalles effectivement compatibles avec cette place. La colonne blanche peut être la deuxième, la troisième, la quatrième, la cinquième ou la sixième : aux extrémités, il manquerait un côté à l'une des affiches.
Pour une place blanche fixée, Nora résout séparément les deux côtés. Si la deuxième colonne est réservée, la gauche ne contient que la première barre, haute de deux : son affiche vaut au plus deux. À droite, les colonnes trois et quatre donnent huit, davantage que toute autre bande de ce côté ; le total atteint dix. Réserver plutôt la troisième colonne donne au plus deux à gauche, par la première colonne ou les deux premières à hauteur un, et six à droite, par les colonnes six et sept. Le total tombe à huit. La note n'a pourtant retiré qu'une colonne dans chacun des deux cas : c'est la position de cette coupure qui change les possibilités offertes aux deux affiches.
Jeanne teste les trois places encore ouvertes au lieu de prolonger par intuition le seul maximum initial. Si la quatrième colonne reste blanche, la troisième donne au plus quatre à gauche, tandis que les colonnes six et sept donnent six à droite : total dix. Si la cinquième reste blanche, les colonnes trois et quatre donnent huit à gauche et six et sept donnent six à droite : total quatorze. Si la sixième reste blanche, les colonnes trois et quatre gardent huit, mais il ne reste à droite que la septième, d'aire trois : total onze. Elle inscrit ainsi, pour les cinq places de la note dans leur ordre, dix, huit, dix, quatorze et onze. Une affiche de gauche ne peut utiliser les hauteurs situées à droite de la note pour améliorer son chiffre.
Camille remet donc deux rectangles précis avec la cinquième colonne vide : positions trois à quatre à hauteur quatre, puis six à sept à hauteur trois. Leurs aires huit et six font quatorze sans surface commune. Ce n'est pas seulement un assemblage possible. Pour n'importe quelle place de note, aucune paire ne peut dépasser la somme des deux maxima calculés sur ses côtés indépendants ; la liste exhaustive des cinq places borne cette somme par quatorze. La paire choisie atteint la borne. Un brouillon plaçait la note en quatrième et conservait pourtant le rectangle trois à quatre : il utilisait la colonne annoncée blanche. Jeanne barre ce brouillon, sans lui accorder fictivement l'aire huit.
L'hôte précise enfin que chaque affiche doit offrir au moins cinq unités d'aire, car deux messages différents doivent être lisibles dans les deux panneaux. Nora ne transforme pas cette limite en seuil sur la somme : dix au total pourrait masquer une affiche d'aire deux et une autre d'aire huit. Aux places blanches deux et trois, le maximum de gauche reste deux ; à la quatrième, il reste quatre ; à la sixième, le maximum de droite n'est que trois. Seule la cinquième laisse simultanément au moins cinq de chaque côté, avec huit et six effectivement réalisés. Le choix demeure donc possible sous la nouvelle exigence, mais pour une raison plus forte que son seul total quatorze. La fiche remet les deux intervalles et la colonne réservée, pas seulement une aire agrégée.
Le dossier final distingue une affiche proposée, une contrainte de largeur et une version des sept hauteurs. Pour la feuille initiale sans largeur minimale, Nora remet colonnes trois et quatre, hauteur quatre, aire huit. Si la commande exige au moins trois colonnes sur cette même feuille, elle remet la largeur entière à hauteur un, aire sept. Si la cinquième barre est réellement corrigée à deux, elle remet colonnes trois à sept, hauteur deux, aire dix. Chaque choix a sa propre liste de plafonds, son intervalle et le calcul qui l'autorise ; aucun n'est une promesse de capacité d'un rangement commercial.
Jeanne ferme le carnet après avoir conservé les anciennes valeurs barrées et les nouvelles versions séparées. La petite correction de hauteur n'a pas été convertie en centimètres, en charge supportée ou en instruction de montage. Les trois pages de mobilier n'attestent que leur catégorie ; le rectangle maximal est une propriété du profil fictif annoncé. Une prochaine personne pourra refaire le produit largeur fois hauteur minimale pour n'importe quel intervalle et comprendre pourquoi déplacer une seule barre, même sans changer l'inventaire total, a modifié la décision remise.