Nora reçoit six fiches de papier pour une préparation créée. Dans leur ordre d'arrivée, elles portent les nombres trois, un, quatre, deux, cinq et deux. Les deux fiches portant deux restent distinctes : la première est à la quatrième place, la seconde à la sixième. Nora veut parfois retenir une progression, parfois répartir toutes les fiches entre plusieurs progressions. Paul propose de trier les six nombres. Cette opération produirait une liste différente ; elle n'a pas encore répondu aux choix qui doivent conserver l'ordre reçu.
Les nombres sont des repères abstraits, sans température, durée ni quantité de service. Dans la première commande, une progression est strictement croissante : chaque nombre retenu est plus grand que celui qui le précède. Les fiches retenues gardent l'ordre de leurs positions initiales, mais peuvent laisser des fiches intermédiaires de côté. Une autre commande autorisera expressément les égalités. Aucune valeur n'est corrigée ou déplacée. Les méthodes de sous-suites et de partition sont classiques, sans invention revendiquée.
Les sources attestent seulement des catégories d’outils d’écriture. Les valeurs, positions et choix sont définis ici ; aucune performance, méthode d’écriture ou règle de tri des marques n’est reprise.
Platinum Pen : stylos.
Aurora : stylos.
Esterbrook : stylos.
La progression remise ne peut pas être obtenue par un tri silencieux
Paul trie les nombres en un, deux, deux, trois, quatre, cinq. Cette liste ne descend pas, mais elle échange les positions des fiches et conserve même une égalité, interdite dans la commande stricte. Nora la refuse pour la sélection voulue. Elle peut retenir les positions deux, quatre et cinq : les nombres un, deux, cinq y arrivent dans cet ordre et augmentent strictement. Les positions une, trois et cinq donneraient aussi trois, quatre, cinq. Il ne suffit donc pas d'annoncer une longueur pour désigner quelle progression sera effectivement remise.
Nora cherche le plus grand nombre de fiches qu'elle pourrait conserver ensemble. Pour chaque position, elle compte une progression qui finit précisément sur cette fiche. La première fiche trois peut donner une longueur un. La deuxième, un, ne peut suivre trois et garde également un. Quatre peut suivre l'une des deux fiches précédentes : sa meilleure longueur est deux. Le premier deux peut suivre un, mais ni trois ni quatre ; il reçoit lui aussi deux. Cinq peut prolonger une progression de longueur deux, et reçoit trois. Le dernier deux ne peut prolonger le premier deux, dont la valeur lui est égale : sa meilleure longueur reste deux.
Les meilleures longueurs par position sont donc un, un, deux, deux, trois, deux. Nora justifie leur calcul par une règle qui regarde toutes les fiches précédentes de valeur plus petite : une progression finissant ici est l'une de leurs progressions, prolongée d'une fiche. Si aucune ne convient, la fiche seule donne un. Prendre la plus grande longueur précédente autorisée donne la meilleure arrivée à cette position. Puisque toute progression finit sur l'une des six fiches, la plus grande des six longueurs, trois, est le maximum de la sélection entière.
La progression un, deux, cinq atteint ce maximum. Nora choisit celle des positions deux, quatre et cinq, parce que sa remise doit commencer par la fiche un et utiliser le premier deux. Paul ne conserve pas le deuxième deux à sa place : il est arrivé après cinq et ne peut le précéder dans la même progression. Une fois les positions choisies, la remise porte leurs identités et leurs valeurs. Elle laisse trois fiches de côté sans transformer celles-ci en valeurs corrigées de la progression remise.
Une liste de fins possibles n’est pas nécessairement une progression reçue
Pour calculer les longueurs sans garder toutes les progressions, Nora conserve la plus petite valeur finale possible pour chaque longueur atteinte. Après trois, sa liste est trois. Après un, elle devient un : une progression d'une fiche peut maintenant finir plus bas. Quatre ajoute une fin de longueur deux, donc la liste un, quatre. Le premier deux remplace cette deuxième fin par deux. Cinq ajoute une fin de longueur trois, donnant un, deux, cinq. Le dernier deux ne crée pas une longueur supplémentaire et remplace seulement la fin de longueur deux par cette dernière occurrence.
La liste finale de valeurs un, deux, cinq ressemble à la progression choisie. Ses occurrences actuellement retenues comme fins sont pourtant la deuxième fiche, la sixième et la cinquième. Ces positions deux, six, cinq ne sont pas dans l'ordre d'arrivée. La deuxième valeur de la liste a été remplacée après que cinq avait déjà établi une progression de longueur trois. Nora refuse donc de remettre directement ces trois occurrences comme une sélection. Chaque fin possède une progression valable de sa propre longueur ; cela ne garantit pas que les fins conservées séparément appartiennent ensemble à une seule progression.
Quand cinq est arrivé, Nora a gardé auprès de cette fiche le précédent qui permettait sa longueur trois : le premier deux, à la quatrième place. Celui-ci gardait un à la deuxième. En suivant ces liens depuis cinq, elle retrouve les positions cinq, quatre, deux, puis les remet dans l'ordre deux, quatre, cinq. Le remplacement ultérieur de la fin de longueur deux par la sixième fiche ne réécrit pas ces liens anciens. Elle peut donc calculer une longueur avec la liste de fins, puis livrer une progression réelle avec les liens conservés, sans demander à la dernière liste de jouer les deux rôles.
Une fin plus petite sert au calcul parce qu'elle laisse au moins autant de possibilités de prolongement qu'une fin plus grande de même longueur. Une fiche future qui pourrait suivre quatre pourrait également suivre deux. Cela ne rend pas l'ancienne progression fausse ni ne prouve que deux appartienne au chemin déjà choisi pour cinq. Nora conserve cette domination sur les prolongements comme raison du remplacement dans son outil de calcul, et les anciennes identités comme raison de la reconstruction. Le même nombre deux peut remplacer une mémoire de fin sans déplacer rétrospectivement une fiche dans une sélection déjà attestée.
Répartir toutes les fiches demande un autre minimum
Une nouvelle commande ne laisse aucune fiche de côté. Nora doit répartir les six positions entre des groupes dont chacun est strictement croissant dans l'ordre reçu. Elle propose trois groupes : les positions une, trois et cinq donnent trois, quatre, cinq ; les positions deux et quatre donnent un, deux ; la sixième fiche deux reste seule. Tous les groupes répondent à l'ordre strict, et chaque identité apparaît une seule fois dans la partition. Cette remise contient trois progressions, au lieu d'une progression de trois fiches.
Deux groupes ne pourraient pas suffire. Les positions une, quatre et six donnent trois, deux, deux dans l'ordre reçu, une suite qui ne monte jamais. Une progression strictement croissante ne peut contenir deux de ces trois fiches : trois avant deux descendrait, et deux avant deux ne monterait pas. Chacune doit donc recevoir un groupe différent. Nora dispose d'une borne de trois groupes que sa partition atteint. Ce témoin ne dépend ni d'un tri des fiches ni du nombre de valeurs différentes ; il utilise trois occurrences et leurs comparaisons dans l'ordre donné.
Pour construire ce genre de partition, elle peut attribuer à chaque fiche la longueur de la plus longue suite non croissante qui finit à sa place. Les longueurs présentes sont un, deux, un, deux, un, trois. Deux fiches de même longueur, dans leur ordre reçu, doivent monter strictement. Sinon la seconde pourrait prolonger une suite non croissante finissant sur la première et recevrait une longueur supérieure. Réunir les fiches de même longueur donne donc effectivement les trois groupes retenus. La borne par une suite non croissante et la construction par ces longueurs ferment ici le minimum, sans supposer qu'une progression maximale aurait déjà réparti les autres fiches.
Le maximum trois des fiches conservées et le minimum trois des groupes coïncident dans cette liste, mais ne répondent pas à la même question. Sur la liste cinq, quatre, trois, deux, un, une sélection croissante ne pourrait garder qu'une fiche, tandis que la partition stricte exigerait cinq groupes. Sur un, deux, trois, quatre, cinq, la sélection garderait cinq fiches et un seul groupe suffirait à tout répartir. Nora garde ces deux commandes séparées. Elle ne choisit pas le nombre de groupes en recopiant la longueur d'une sélection qui abandonne les fiches restantes.
Choisir le plus petit dernier nombre disponible peut ouvrir un groupe inutile
Nora examine une liste plus courte, deux, un, trois, deux. Elle ajoute les fiches dans l'ordre à des groupes strictement croissants, en regardant seulement leurs derniers nombres. Deux commence un premier groupe et un un second. Trois pourrait suivre l'un ou l'autre. Paul choisit le groupe terminé par un, parce que ce dernier nombre est le plus petit. Les groupes deviennent deux seul et un, trois. Le dernier deux ne peut suivre ni deux, égal à lui, ni trois, plus grand. Son choix a donc ouvert un troisième groupe.
Nora reprend le moment où trois pouvait rejoindre deux. Elle l'y place, laissant les groupes deux, trois et un. Le dernier deux rejoint alors un, pour former un, deux. Deux groupes suffisent, avec les quatre identités présentes une fois. Une suite non croissante deux, un interdit un groupe unique, donc ce nombre deux est minimal. Le choix local du plus grand dernier nombre encore strictement inférieur à trois a conservé une place plus basse pour la fiche suivante. La préférence contraire n'était pas une conséquence de la demande de croissance ; elle a consommé la possibilité dont le dernier deux avait besoin.
Elle ne transforme pas ce cas en droit d'annuler n'importe quelle décision sans conserver les groupes reçus. Dans la branche où Paul avait déjà fixé un, trois, la remise comporte encore trois groupes. Pour obtenir la partition à deux, Nora doit être autorisée à reprendre l'affectation de trois. Elle l'indique comme correction de cette affectation, puis transmet les deux listes complètes. Les nombres d'origine n'ont pas changé ; l'identité de leur groupe a changé. Le passage de trois groupes à deux n'est donc pas une diminution obtenue en effaçant la dernière fiche de la commande.
Autoriser les égalités change les relations qui empêchent une réunion
Une branche séparée contient deux, deux, un, trois. Sous la règle strictement croissante, une sélection peut garder deux puis trois, ou un puis trois, soit deux fiches. Les deux premiers deux ne peuvent être conservés successivement. Si Nora demande au contraire une progression qui ne descend jamais, les positions une, deux et quatre donnent deux, deux, trois : trois fiches deviennent possibles. La même égalité était un obstacle dans la première commande et une transition permise dans la seconde. Elle garde le mot strictement dans la première feuille plutôt que d'appeler ces deux choix croissants sans distinction.
La partition change aussi. Dans la règle stricte, les trois premières fiches deux, deux, un doivent appartenir à trois groupes différents. Trois peut rejoindre l'un des groupes, mais le minimum reste trois. Avec les égalités autorisées, un groupe deux, deux, trois reçoit les positions une, deux et quatre, tandis que un reste seule : deux groupes suffisent. Un groupe unique est impossible, puisque le passage de deux à un descend. Nora remet donc deux avec cette permission et trois avec l'autre. Le témoin de séparation n'est plus une suite non croissante : une égalité ne peut plus interdire le partage d'un groupe.
Le plus grand nombre retenu ne minimise pas toujours le poids des fiches retirées
Nora revient aux six valeurs trois, un, quatre, deux, cinq, deux. Elle attribue les poids un, dix, un, un, un et cent aux six identités. Retirer une fiche coûte son poids ; celles conservées doivent encore former une sélection strictement croissante. Ces poids sont des points donnés pour l'exercice, sans prix réel ni importance attribuée à des personnes. Nora veut cette fois le plus petit coût retiré, et non le plus petit nombre de fiches retirées. Les valeurs et l'ordre restent intacts dans les deux commandes.
La meilleure sélection de trois fiches ne peut garder la sixième, qui porte deux : avant elle, seul un à la deuxième place peut précéder strictement deux, sans autre valeur entre un et deux dans la liste. Pour trois fiches, Nora peut retenir un avec quatre puis cinq, ou un avec le premier deux puis cinq ; le poids conservé vaut douze. La sélection trois, quatre, cinq ne conserve que trois points. Le total des six poids vaut cent quatorze. Même la meilleure sélection de longueur trois retire donc cent deux points.
Nora conserve au contraire un à la deuxième place et deux à la sixième. Leur poids vaut cent dix, et les quatre fiches retirées ne coûtent ensemble que quatre. Toute sélection ne gardant pas la dernière fiche ne pourrait conserver plus que les quatorze points des cinq premières réunies. Une sélection qui la garde ne peut lui adjoindre que un, ou la garder seule ; le poids cent dix est donc le maximum possible. Nora remet ces deux identités pour la commande pondérée. Elle retire quatre fiches au lieu de trois, tout en abaissant leur coût de cent deux à quatre. Le minimum de compte n'a pas décidé le minimum sous ces poids.
Une vérification par positions peut conserver le plus grand poids de progression finissant sur chaque fiche, au lieu de sa plus grande longueur. La fiche nouvelle ajoute son poids au meilleur total parmi les valeurs précédentes plus petites, ou commence seule si aucun précédent ne convient. Nora utilise ici les points positifs donnés ; elle ne confond pas la place six et sa valeur deux avec le poids cent de cette identité. Les longueurs et les poids demandent des mémoires différentes, puis les mêmes liens de reconstruction permettent de nommer les fiches effectivement choisies pour chacun des objectifs.
Une limite de deux fiches par groupe invalide une affectation auparavant correcte
Une dernière partition porte sur toutes les six fiches, avec ordre strict dans chaque groupe, mais interdit désormais plus de deux fiches dans un groupe. La partition trois, quatre, cinq ; un, deux ; deux seul n'est plus admise : son premier groupe en contient trois. Paul reprend une affectation à mesure des arrivées et ferme chaque groupe après sa deuxième fiche. Trois puis quatre ferment son premier ; un puis le premier deux ferment son deuxième. Cinq ouvre un troisième ; le dernier deux ne peut suivre cinq et ouvre un quatrième. Cette procédure remet quatre groupes, tous autorisés, mais pas encore prouvés minimaux.
Nora peut revoir toute l'affectation avec la liste entière. Les positions une et trois donnent trois, quatre ; deux et six donnent un, deux ; quatre et cinq donnent deux, cinq. Les trois paires montent strictement et contiennent exactement deux fiches chacune. Aucun groupe ne dépasse la limite et aucune fiche ne disparaît. Deux groupes ne pourraient couvrir six fiches lorsque chacun en contient au plus deux. Trois est donc le minimum sous cette limite. Nora choisit ces trois paires plutôt que les quatre groupes de la procédure d'arrivée. Cette nouvelle affectation retire notamment le premier deux du groupe avec un pour lui laisser rejoindre cinq.
Le défaut de la procédure ne venait pas d'un mauvais contrôle de la croissance à l'intérieur de ses quatre groupes. Il venait de décisions prises sans reprendre les places déjà consommées dans des groupes limités. Une place dans un groupe de deux peut devenir indisponible même si sa dernière valeur était idéale pour une fiche future. Nora garde donc la limite de taille avec les décisions d'affectation. Elle ne transporte pas sans contrôle une règle de choix de dernier nombre vers une commande qui ferme les groupes après deux fiches. Les trois paires restent la remise calculée avec possibilité de revoir l'ensemble.
Deux longueurs opposées ne peuvent pas rester petites dans une liste trop grande
Nora compare enfin deux limites imposées ensemble : aucune sélection strictement croissante de trois fiches, et aucune sélection non croissante de trois fiches. Pour chaque position, elle inscrit les deux meilleures longueurs qui y finissent, croissante stricte puis non croissante. Deux positions différentes ne peuvent recevoir le même couple. Si la valeur de la première est plus petite que celle de la seconde, la deuxième peut prolonger sa progression croissante ; sinon elle peut prolonger sa suite non croissante. Dans les deux cas, l'une de ses longueurs dépasse celle de la première.
Si les deux longueurs sont au plus deux partout, leurs couples peuvent seulement être un, un ; un, deux ; deux, un ; deux, deux. Il y a quatre couples, donc au plus quatre fiches. Nora peut remplir cette limite avec deux, un, quatre, trois : la plus grande sélection croissante a deux fiches, et la plus grande non croissante également. Ajouter une cinquième fiche, de n'importe quelle valeur, oblige l'une des deux longueurs à atteindre trois. Nora refuse ainsi une commande de cinq fiches gardant simultanément les deux interdictions, sans tester une valeur supplémentaire après l'autre pour espérer éviter les deux relations.
Ce contrôle ne sélectionne pas automatiquement une progression précise lorsqu'il en garantit une. Il oblige seulement l'une des deux familles à dépasser la longueur deux. Pour sa liste de six, Nora a remis séparément une progression de trois et un témoin non croissant de trois ; leurs rôles ne sont pas devenus identiques. Une limite sur les deux formes et une préférence pour les identités choisies sont deux demandes différentes. Elle conserve les couples de longueurs comme preuve du refus sur cinq, et les positions des fiches comme preuve des remises qu'elle a réellement retenues.
La feuille finale garde ses six valeurs dans l'ordre reçu, avec des sélections et des groupes nommés séparément. Nora peut remettre les positions deux, quatre et cinq pour le maximum de longueur, deux et six pour le poids, puis trois paires pour la partition limitée. Paul retrouve les fiches abandonnées dans les deux premières remises et toutes les fiches attribuées dans la troisième. Aucun nombre n'a été corrigé pour faire monter une liste, aucune occurrence égale n'a été échangée silencieusement. Les décisions portent sur les positions conservées et les permissions qui expliquent leurs comparaisons.