Camille reçoit une feuille fictive de rangement divisée en lignes et en colonnes. Chaque case porte un entier. Elle veut retrouver un repère demandé en ouvrant des cases une à une, puis compter celles qui ne dépassent pas un seuil. Nora ne lui donne aucune mesure de boîte ou d'objet : les repères et leurs adresses sont stipulés sur papier. Deux ordres seront garantis dans la feuille reçue, sans transformer toutes ses cases en une seule liste croissante.
Orthex présente des boîtes de rangement.
keeeper présente une rubrique de rangement.
What More UK présente des rubriques de boîtes et de rangement alimentaire.
Ces catégories situent la feuille ; aucun produit, dimension ou procédé réel de rangement n'est adapté. Les images ne sont pas examinées.
La feuille possède quatre lignes, numérotées zéro à trois, et quatre colonnes dans le même sens de gauche à droite. La première ligne contient 1, 4, 7, 11 ; la deuxième 2, 5, 8, 12 ; la troisième 3, 6, 9, 16 ; la dernière 10, 13, 14, 17. Chaque ligne ne descend pas vers la droite et chaque colonne ne descend pas vers le bas. Les égalités resteraient permises dans une autre feuille. Une ouverture révèle le nombre d'une case ; les indices seuls ne révèlent pas les nombres cachés. La recherche en escalier dans un tableau ainsi ordonné est classique, sans invention revendiquée.
Un coin permet de retirer une ligne ou une colonne entière
Camille cherche huit. Elle commence en haut à droite, ligne zéro et colonne trois, où elle lit onze. Tous les nombres au-dessous dans cette colonne sont au moins onze : huit ne peut s'y trouver. Elle retire la colonne trois de la région encore possible et ouvre la case voisine vers la gauche, qui porte sept. Toute la première ligne restante porte au plus sept ; huit ne peut y figurer. Camille retire cette ligne et descend dans la même colonne deux. Elle lit huit à la ligne un et remet cette adresse. Trois ouvertures ont trouvé un repère sans classer les seize cases.
Les deux décisions utilisent deux garanties différentes. Onze excluait la colonne à partir de la case ouverte, par l'ordre vertical ; sept excluait la ligne jusqu'à cette case, par l'ordre horizontal. Nora conserve au cours du parcours un rectangle de lignes et de colonnes encore candidates. La case ouverte reste son coin supérieur droit. Ainsi, les parties d'une ligne ou d'une colonne exclues par une comparaison sont exactement celles qui bordent ce rectangle. Camille ne généralise pas une seule comparaison à toute la feuille, puisque les régions précédemment retirées avaient leurs propres justifications.
Camille propose d'ouvrir plutôt la case centrale qui porte cinq. Si le repère demandé vaut six, elle souhaiterait choisir aussitôt un côté unique. Nora lui donne deux petites feuilles autorisées. La première porte les lignes 1,2,6 ; 3,5,7 ; 4,8,9. La seconde 1,2,4 ; 3,5,7 ; 6,8,9. Toutes deux respectent les ordres des lignes et des colonnes, et leur centre vaut cinq. Six se trouve pourtant en haut à droite dans la première, en bas à gauche dans la seconde. Camille retire sa décision centrale qui jetterait l'une de ces régions entières. Les cases incomparables au centre ne sont pas réunies par un seul sens d'ordre.
Nora garde le coin supérieur droit pour le parcours convenu. Depuis lui, une valeur trop grande ferme une colonne, une valeur trop petite ferme une ligne. Elle n'annonce pas que toute autre méthode serait impossible : elle retire seulement l'élimination que Camille venait de justifier par la seule comparaison centrale. Un choix d'ouverture doit préciser les cases que sa comparaison permet effectivement d'écarter. La place centrale ne donne pas spontanément les deux retraits simples du coin, même lorsqu'elle divise visuellement la feuille en quatre régions égales.
Une recherche peut terminer par un refus justifié
Pour quinze, Camille ouvre onze puis douze en descendant dans la dernière colonne. Ces deux nombres sont trop petits et retirent leurs lignes. Elle arrive à seize, trop grand, puis se déplace à gauche sur neuf. Cette fois, la troisième ligne restante est trop basse et peut être retirée. Camille descend sur quatorze, encore inférieur à quinze, et sort après avoir retiré la dernière ligne. Les cinq ouvertures onze, douze, seize, neuf, quatorze ne contenaient pas quinze. Nora remet son absence parce que chaque case a été éliminée par un ordre garanti, et non parce qu'un essai limité aurait simplement échoué.
La case dix-sept, en bas à droite, n'a pas été ouverte pendant ce parcours. Elle avait pourtant déjà été exclue lorsque seize avait fermé la dernière colonne des deux lignes restantes : dix-sept y était au moins seize. Camille conserve cette explication dans le reçu d'absence. Elle ne doit pas ouvrir cette case une seconde fois pour justifier le même retrait. En revanche, si l'ordre vertical n'avait pas été garanti, la comparaison à seize n'aurait pas permis d'écarter la case située au-dessous. Le nombre d'ouvertures économisées vient de ce renseignement reçu, pas d'un droit de sauter une case inconnue sans motif.
Pour dix, le parcours remplit réellement sept ouvertures : onze, sept, huit, neuf, quatorze, treize, dix. Chaque mouvement a consommé une ligne ou une colonne encore candidate avant la dernière égalité. Dans un tableau de quatre par quatre, un parcours qui ne revient jamais vers le haut ou vers la droite ouvre au plus sept cases : trois descentes et trois déplacements à gauche peuvent suivre son ouverture initiale. Camille garde sept comme borne de ce parcours, et le cas dix montre qu'il peut l'atteindre. Nora ne fait pas de cette réalisation une preuve que toutes les méthodes possibles exigeraient sept ouvertures.
Lire les lignes à la suite ne fournit pas un nouvel ordre global
Camille copie les lignes du tableau les unes après les autres, en commençant par celle du haut, et veut effectuer une recherche binaire dans cette liste. La première ligne finit par onze mais la suivante commence par deux. La liste copiée redescend donc à leur frontière, alors que chaque ligne prise séparément respecte sa garantie. Nora refuse l'ordre global présumé. Les coordonnées d'une case dans le tableau ne peuvent être remplacées par une place dans une seule liste triée sans avoir vérifié une propriété plus forte que celles reçues.
L'échec est rempli pour le repère trois. Une recherche binaire par bornes dans les seize positions copiées ouvre d'abord la position sept, douze ; puis la position trois, onze ; puis un, quatre ; puis zéro, un. Elle termine sans trouver trois, qui figurait pourtant à la ligne deux et colonne zéro. Après douze, son retrait de toute la moitié droite était injustifié : les positions suivantes pouvaient commencer par des nombres inférieurs. Camille garde l'absence obtenue par cet essai comme une erreur du protocole, puis retrouve trois par le parcours en escalier. Elle ne modifie pas la donnée trois pour faire correspondre les deux réponses.
Une branche ne promet plus que l'ordre de chaque ligne. Sa feuille contient 1,4,7 ; 2,8,9 ; 3,5,10. Les lignes sont croissantes, mais la colonne centrale monte de quatre à huit puis descend à cinq. Chercher cinq par le coin supérieur droit lit sept, quatre, huit, deux, trois, puis sort sans résultat. La présence de cinq en dernière ligne et colonne centrale montre le défaut. Camille refuse donc de transporter la preuve d'absence précédente vers cette nouvelle permission. Elle peut chercher dans chaque ligne séparément, puisqu'elle possède encore leurs trois ordres ; elle ne reçoit plus le retrait vertical de colonne.
Compter sous un seuil garde une frontière au lieu de s'arrêter à une égalité
Camille revient au premier tableau et demande combien de cases portent au plus huit. Elle commence encore à droite de la première ligne, déplace sa frontière à gauche tant qu'un nombre dépasse huit, puis compte toutes les cases situées jusqu'à cette frontière. La première ligne en apporte trois, 1,4,7. La deuxième en apporte trois aussi, 2,5,8. La troisième ne peut en apporter davantage : à sa colonne deux, neuf dépasse le seuil et la frontière recule jusqu'à six, donnant deux cases. Dans la dernière ligne, treize puis dix dépassent huit ; la frontière sort à gauche et donne zéro.
Les quatre contributions trois, trois, deux, zéro totalisent huit. La frontière n'est jamais repartie vers la droite entre deux lignes : une colonne rejetée sur une ligne possède au-dessous une valeur au moins aussi grande et demeure rejetée sous le même seuil. Camille a donc pu obtenir le total en suivant un seul déplacement de frontière à travers la feuille. Elle ne s'est pas arrêtée lorsqu'elle a rencontré la première égalité huit. L'égalité avait permis d'accepter un préfixe de ligne, mais les lignes suivantes gardaient encore leurs contributions à examiner pour la nouvelle commande.
Nora distingue ce compte du seul nombre d'adresses ouvertes. Camille a pu accepter trois cases en ouvrant seulement la dernière de leur préfixe. Sous l'ordre de cette ligne, les deux précédentes satisfaisaient nécessairement le seuil. La commande compte des cases, non des comparaisons. Nora garde les nombres de contributions auprès des frontières atteintes. Elle ne donne pas cinq, le nombre d'ouvertures d'une autre recherche d'absence, comme total du tableau sous huit : ces deux protocoles ne comptaient pas la même chose et n'interrogeaient pas le même repère.
Une valeur répétée demande deux frontières différentes
Une autre feuille ordonnée porte 1,3,8,8 ; 2,8,8,10 ; 8,8,9,12 ; 8,11,13,14. Camille veut cette fois le nombre exact d'apparitions de huit. La frontière des nombres au plus huit donne quatre cases dans la première ligne, trois dans la deuxième, deux dans la troisième et une dans la dernière : total dix. Elle ne peut remettre dix comme fréquence de huit, car les nombres un, deux et trois sont encore inclus dans ce total. Le seuil inclusif portait aussi sur toutes les valeurs inférieures.
Nora suit séparément la frontière des nombres strictement inférieurs à huit. Elle obtient deux, un, zéro, zéro, soit trois. Retrancher ces trois cases du total dix laisse sept apparitions exactes de huit. Les frontières diffèrent dans les lignes où l'égalité apparaît, et les deux permissions doivent donc rester écrites auprès de leurs comptes. Camille remet sept sans ouvrir une à une les sept cases égales. Une réponse d'existence aurait pu s'arrêter à la première ; une fréquence exacte a exigé un autre couple de recherches, chacune avec sa propre inégalité.
Si Camille veut aussi toutes les adresses de huit, les deux frontières désignent sur chaque ligne les positions situées entre leurs fins de préfixes. Dans la première, colonnes deux et trois ; dans la deuxième, un et deux ; dans la troisième, zéro et un ; dans la dernière, zéro. Nora remet ces sept couples ligne-colonne. Le compte sept seul ne permettait pas de choisir leur répartition : ce sont les deux limites conservées pour chaque ligne qui l'ont donnée. Camille garde donc les frontières par ligne lorsqu'elle accepte la commande d'adresses, plutôt que leur seule somme globale dix moins trois.
Le huitième repère classé se cherche dans les valeurs possibles
Camille revient au premier tableau, dont les repères sont des entiers entre un et dix-sept. Elle demande le huitième nombre après classement des seize cases, en conservant leurs occurrences. Nora n'applique pas la recherche binaire à leur copie non triée. Elle l'applique aux valeurs possibles et pose chaque fois la question du nombre de cases au plus égal à la valeur essayée. Ce nombre ne peut diminuer lorsque la valeur augmente. Elle cherche la plus petite valeur pour laquelle le compte atteint au moins huit.
Le milieu neuf donne neuf cases ; Nora peut garder la moitié des valeurs jusqu'à neuf. Le milieu cinq n'en donne que cinq, donc elle relève la borne basse à six. Sept en donne sept, ce qui la relève à huit. Huit en donne huit et ferme les deux bornes sur huit. Camille reçoit donc huit comme valeur du rang demandé. Les quatre essais neuf, cinq, sept, huit ont chacun utilisé un parcours de frontière dans le tableau. Nora ne les présente pas comme quatre seules cases ouvertes : le nombre d'essais de valeurs et le coût des questions de compte sont deux unités distinctes du protocole.
La plus petite valeur atteignant le compte huit est nécessaire à la réponse. Neuf satisfaisait déjà le test « au moins huit », mais ne représentait pas le huitième nombre. Camille aurait remis un repère trop haut en conservant le premier seuil qui passait. Pour les valeurs entières stipulées, avancer la borne basse de cinq à six puis de sept à huit garantit qu'aucune valeur possible n'a été perdue entre deux essais. Nora conserve cette permission d'entiers dans la recherche. Elle ne promet pas le même traitement par incrément de un pour un dossier contenant des fractions arbitraires.
Une recherche ordonnée conserve des informations qui peuvent rester incomparables
Nora prépare une feuille test de quatre par quatre où toutes les cases dont ligne plus colonne est inférieur à trois portent zéro, et celles où cette somme dépasse trois portent dix. Les quatre cases de somme trois, en diagonale descendante, peuvent chacune porter quatre, cinq ou six indépendamment des autres. Toutes ces feuilles restent croissantes dans leurs lignes et leurs colonnes : autour de chaque case libre, les comparables immédiatement antérieures sont zéro et les postérieures dix. Les quatre cases libres, elles, ne se trouvent pas au-dessous ou à droite l'une de l'autre.
Camille cherche cinq sur la réalisation où ces quatre cases portent quatre. Si elle en laisse une fermée, Nora peut changer seulement celle-ci en cinq, sans modifier aucun nombre déjà lu ni perdre les deux ordres garantis. Les observations de Camille restent identiques mais la réponse d'existence devient positive. Pour certifier l'absence sur cette famille, il faut donc contrôler chacune des quatre cases libres, directement ou par une information supplémentaire qui n'appartenait pas à la permission initiale. La lecture des zéros et des dix voisins n'a pas fixé leurs quatre valeurs indépendantes.
Cette limite ne dit pas qu'il faut ouvrir seize cases, ni que sept serait le minimum pour toute stratégie. Elle montre ce que la garantie des deux ordres n'a pas fusionné : quatre adresses encore incomparables peuvent porter des réponses différentes tout en conservant les autres observations. Camille garde cette feuille test comme contrôle de sa preuve d'absence. Elle ne transforme pas la forte organisation du tableau en certitude que chaque valeur serait déduite depuis un seul nombre central. Ce garde-fou général de recherche reste séparé des décisions remplies sur les deux feuilles précédentes.
Une sous-feuille conserve les mêmes ordres avec ses propres bornes
Camille reçoit finalement la commande portant sur les lignes un et deux, colonnes un, deux, trois, dans le tableau initial. Les deux lignes de cette sous-feuille sont 5,8,12 et 6,9,16. Sous le seuil neuf, elles apportent chacune deux cases, soit quatre. La frontière peut repartir du coin supérieur droit de ce rectangle plus petit et suivre les mêmes retraits valables. Elle ne commence pas par compter les premières colonnes ou la ligne zéro, car elles n'appartiennent pas au périmètre reçu.
Nora peut contrôler ce résultat depuis des comptes de rectangles ancrés en haut à gauche. Le compte neuf du tableau entier sous neuf perd les trois cases acceptées de la première ligne, puis les trois acceptées de la première colonne, et récupère leur case commune un, qui avait été retranchée deux fois. Neuf moins trois moins trois plus un donne quatre. Camille garde cette combinaison avec les quatre périmètres dont elle provient. Soustraire seulement une première ligne et une première colonne sans rendre leur intersection aurait remis trois, malgré les quatre cases effectivement autorisées dans la sous-feuille.
Une ligne de comparaisons peut partager la recherche en deux régions
Camille essaie une autre recherche pour six sur le tableau initial, avec la permission de lire la ligne médiane plutôt qu'une seule case centrale. Une recherche binaire dans la ligne un, 2,5,8,12, compare d'abord huit, puis cinq, et trouve la séparation entre leurs colonnes un et deux, sans six sur cette ligne. Toutes les cases au-dessus et à gauche de cette séparation portent au plus cinq, tandis que celles au-dessous et à droite portent au moins huit. Nora retire donc ces deux rectangles opposés. Il reste la première ligne dans les colonnes deux et trois, puis les deux dernières lignes dans les colonnes zéro et un. Elle garde les deux régions, et non un côté choisi arbitrairement depuis la seule comparaison centrale cinq.
La région supérieure restante contient sept et onze ; leur recherche ordonnée refuse six. Dans la région inférieure, la première ligne restante porte trois et six : Camille y trouve six à la colonne un, ligne deux. Nora remet cette adresse avec le partage qui l'a conservée. Les rectangles exclus n'avaient pas besoin d'être lus, mais les deux régions survivantes demandaient encore leur recherche. Si Camille s'était arrêtée après le refus supérieur, elle aurait déclaré une absence fausse. Le nombre huit lu sur la ligne médiane a apporté la limite haute qui manquait à la seule comparaison cinq ; la recherche de cette ligne entière a donc changé les régions qu'il était possible d'écarter. Nora conserve cette seconde procédure comme un partage récursif classique, sans lui attribuer automatiquement la borne de sept ouvertures du parcours en escalier.
La dernière remise choisit le tableau initial pour sa recherche à deux ordres et conserve la feuille à colonnes non ordonnées comme cas refusé pour ce protocole. Camille remet l'adresse de huit, le refus de quinze, les huit cases sous huit et la sous-feuille de quatre cases sous neuf avec leurs demandes différentes. Les catégories citées n'ont fourni ni ces nombres ni une garantie d'ordre. Aucun parcours de lecture n'est présenté comme le résultat d'un appareil ou l'organisation mesurée de contenants réels.