Camille prépare six fiches fictives pour un service de papier. Leurs numéros sont un, quatre, huit, huit, douze et quinze. Nora veut retrouver une fiche proche du numéro dix selon une règle portant sur leurs signes binaires. Les deux fiches huit restent deux exemplaires distincts. Aucun appareil ni traitement observé n'est décrit : la feuille est un exercice dont les demandes et les réponses peuvent être contrôlées à la main.
La notice336700 porte la catégorie Drawings.
La notice336800 porte la catégorie Drawings.
La notice336900 porte la catégorie Prints.
Ces catégories seules ont été lues. Aucune image ni méthode d'artiste ne fournit les signes, l'index ou les décisions de cet exercice.
La règle de proximité choisit réellement une autre fiche
Camille écrit tous les numéros sur quatre places binaires, même lorsqu'ils commencent par zéro. Un devient0001, quatre0100, huit1000, douze1100 et quinze1111. Le numéro demandé dix devient1010. La comparaison donne zéro à une place où les deux signes sont identiques et un lorsqu'ils diffèrent : c'est le XOR. Les quatre places du résultat gardent leurs valeurs huit, quatre, deux et un. Nora compare ensuite les entiers ainsi obtenus, pas seulement le nombre de places différentes. Les deux fiches huit donnent donc exactement la même valeur, mais restent disponibles séparément.
Pour dix, les résultats sont onze avec un, quatorze avec quatre, deux avec chaque huit, six avec douze et cinq avec quinze. Nora choisit une fiche huit pour le plus petit résultat. Une recherche par écart numérique aurait donné huit et douze ex aequo, tous deux situés à deux de dix ; une préférence supplémentaire aurait été nécessaire pour les départager. Notre demande XOR les départage déjà : deux est strictement inférieur à six. Camille remet huit avec son résultat deux, sans annoncer que le numéro retrouvé minimise une différence arithmétique que Nora n'a pas choisie.
La fiche la plus éloignée selon cette même règle est quatre, avec quatorze. Prendre le plus grand numéro stocké aurait remis quinze, dont le résultat n'est que cinq. Les réponses proche et éloignée portent ainsi huit et quatre, aucun des deux n'étant une extrémité de la liste numérique un à quinze. Nora garde les six résultats près des deux remises. La présence d'un petit numéro ne le rend pas automatiquement proche de dix : un donne onze. Les entiers reçus servent à écrire les signes ; l'objet effectivement comparé est le résultat de leur combinaison avec la demande.
Un chemin commence par la place qui décide avant toutes les suivantes
Camille construit un index de quatre bifurcations. La première sépare les fiches dont la place huit vaut zéro de celles où elle vaut un. Un et quatre vont à gauche ; les deux huit, douze et quinze à droite. Chaque groupe est ensuite partagé par sa place quatre, puis deux, puis un. Les feuilles donnent les numéros entiers, avec deux exemplaires dans la feuille1000. Une bifurcation ne compare pas deux numéros pivots : elle lit la même place chez toutes les fiches de sa branche. Les effectifs sont deux et quatre sous la première séparation, et leur somme reste six.
Pour chercher la plus petite combinaison avec1010, Nora préfère à chaque bifurcation le signe identique à celui de la demande, s'il reste au moins une fiche dans cette branche. À la place huit, elle choisit donc un et conserve les deux huit, douze et quinze. À la place quatre, elle préfère zéro et conserve les deux huit. Les deux dernières places n'offrent plus de choix entre numéros : la feuille1000 est la seule disponible. Le résultat est0010. Nora peut prendre un des deux exemplaires ; l'index n'a pas choisi leur propriétaire puisqu'ils portent le même numéro dans les données reçues.
Camille justifie pourquoi elle n'a pas à revenir vers la branche abandonnée. À la place huit, un résultat zéro économise huit ; les trois places suivantes ne peuvent ensemble ajouter que sept. À la place quatre, un zéro économise quatre ; les deux suivantes ne peuvent ajouter que trois. Le même contrôle vaut ensuite pour deux et un. Une branche disponible donnant zéro à la première place différente bat donc toute réponse donnant un là, quels que soient les choix plus bas. Sur notre demande, quitter les huit pour douze ou quinze aurait introduit quatre dans le résultat, sans pouvoir le retirer ensuite.
Pour le maximum, Nora préfère le signe opposé. À la première place, la demande vaut un et la branche zéro existe : elle garde un et quatre. À la place quatre, la demande vaut zéro ; la branche un de quatre existe, donc elle la retient. La feuille0100 donne1110, soit quatorze. Les choix restants forcés ne diminuent pas les deux premiers avantages. Camille remet le chemin avec la fiche quatre. Elle refuse de suivre le côté droit partout : à la première place, ce côté aurait au contraire donné zéro dans la combinaison avec dix, perdant huit d'emblée.
Un troisième exemplaire dans l'ordre demande des effectifs, pas seulement des branches présentes
Nora demande maintenant la troisième fiche lorsque les six exemplaires sont rangés par leur résultat avec dix, en comptant les rangs à partir de un. Camille obtient huit, huit, quinze, douze, un, quatre, avec les valeurs deux, deux, cinq, six, onze et quatorze. La réponse est quinze. Le choix proche précédent ne suffit pas : il savait qu'une branche était disponible, sans dire combien de fiches elle contenait. Le second huit occupe réellement le rang deux. Si Camille ne conservait qu'une présence par feuille, elle attribuerait ce rang à quinze et déplacerait la troisième remise vers douze.
Dans l'index, la première branche préférée contient quatre fiches ; le rang trois y reste. La suivante, où la place quatre est identique au zéro de la demande, contient deux fiches, les deux huit. Nora les passe entièrement et cherche désormais le rang un dans l'autre branche. Celle-ci contient douze et quinze. À la place deux, dix porte un ; la branche un de quinze donne un résultat zéro et précède la branche zéro de douze. Nora retient donc quinze. Elle a soustrait deux exemplaires de son rang, et non deux places binaires ni deux numéros différents.
Les rangs trois et quatre appartiennent tous deux à la branche qui avait été évitée par la recherche du minimum. Pour le rang quatre, Nora passe encore les deux huit, mais garde un rang restant de deux. La branche de quinze n'a qu'un exemplaire ; elle le passe et rejoint douze. La première bifurcation conserve pourtant le même côté pour ces deux recherches : quatre fiches y précèdent les deux dont la place huit diffère. Camille n'annonce donc pas un ordre permanent des branches gauche et droite. Leur priorité dépend du signe demandé, et leurs effectifs servent à retirer une plage entière de rangs sans changer cette priorité.
Une borne ferme la recherche sans compter la fiche située juste sur elle
Une autre demande veut toutes les fiches dont la combinaison avec dix est strictement inférieure à six. Nora écrit six0110. À la place huit, la borne vaut zéro ; tout résultat commençant par un serait déjà trop grand, elle doit garder la branche donnant zéro. À la place quatre, la borne vaut un. Tous les résultats commençant par00 sont alors plus petits, quelles que soient leurs deux dernières places : Nora ajoute les deux huit d'un seul coup. Elle poursuit seulement dans la branche01 pour contrôler les fiches encore susceptibles d'être sur la borne ou en dessous.
Il reste douze et quinze. À la place deux, la borne vaut un ; les résultats010 de la branche de quinze sont déjà inférieurs, et Nora ajoute cet exemplaire. Elle continue vers le résultat011 de douze. À la dernière place, la borne vaut zéro : seule l'égalité peut rester, aucun résultat plus petit de cette branche n'est disponible. Le résultat complet de douze est0110, exactement six. Nora ne l'ajoute pas à une réponse strictement inférieure. La remise contient les deux huit et quinze, soit trois exemplaires. Les deux et cinq figurent sur la feuille ; six n'est pas rendu inférieur par le fait d'avoir atteint sa dernière place.
Si Nora autorise ensuite une combinaison au plus égale à six, douze devient un quatrième exemplaire admissible. Camille change cette seule frontière et garde les deux huit et quinze. Elle ne remplace pas leur compte trois par le nombre de résultats distincts deux, car la demande porte toujours sur des fiches. À l'autre extrémité, une borne strictement inférieure à zéro ne retient aucune fiche, et une borne strictement inférieure à seize retient les six : toute combinaison de quatre places est entre zéro et quinze. Cette borne seize a besoin d'une place supplémentaire pour être écrite, elle ne peut pas être tronquée en0000.
Retirer un exemplaire ne retire pas encore son chemin
Camille retire une seule des deux fiches huit. Elle diminue de un l'effectif de sa feuille et de chaque branche traversée. La première branche droite passe de quatre à trois ; la sous-branche100 passe de deux à un. Nora reprend sa demande proche de dix et reçoit encore huit, avec deux. Couper le chemin1000 dès le premier retrait aurait effacé le deuxième exemplaire resté sur la table. La nouvelle liste par combinaison est huit, quinze, douze, un, quatre. Sa troisième fiche est désormais douze, et non quinze, parce qu'un rang a effectivement disparu avant eux.
Un second retrait de huit vide enfin la feuille. Nora doit alors chercher la proximité parmi un, quatre, douze et quinze. La branche droite existe encore, mais sa sous-branche où la place quatre vaut zéro n'a plus de fiche. Nora prend l'autre sous-branche, où se trouvent douze et quinze, puis choisit à la place deux le un identique à celui de dix. Elle remet quinze, avec cinq, devant douze et six. Un index qui garderait un pointeur ancien vers1000 sans vérifier son effectif positif répondrait huit absent. La trace historique de la feuille ne donne aucun exemplaire disponible au présent.
Camille insère ensuite dix, écrit1010, dans cette liste sans huit. Elle crée ou réactive le chemin correspondant et augmente ses quatre effectifs. Nora reçoit maintenant dix lui-même avec une combinaison nulle. Cette insertion traverse certaines branches que le retrait de huit avait vidées, mais la feuille finale est différente :1010 ne remplace pas un exemplaire1000. Le résultat zéro est atteint parce que les quatre signes coïncident, non parce que la demande a été déclarée présente au sommet. Camille garde la liste actuelle un, quatre, dix, douze et quinze pour contrôler le résultat et les rangs de cette nouvelle version.
Une étiquette commune transforme les demandes autant que les réponses
Une branche indépendante repart des six fiches initiales, avec les deux huit. Nora veut remplacer chaque numéro x par x combiné avec cinq. Cinq vaut0101. Les numéros affichés deviennent quatre, un, treize, treize, neuf et dix. Camille pourrait refaire leurs feuilles, mais conserve ici les anciens numéros comme places physiques et une étiquette commune cinq. Pour demander le numéro dix dans l'affichage nouveau, elle doit chercher physiquement avec dix combiné avec cinq, soit quinze. La règle vient de la compensation de deux occurrences de cinq : comparer dix à x combiné avec cinq donne le même résultat que comparer quinze à x.
La demande physique quinze donne quatorze pour un, onze pour quatre, sept pour chaque huit, trois pour douze et zéro pour quinze. Le minimum rejoint donc l'ancienne feuille quinze. Nora doit remettre son numéro affiché, quinze combiné avec cinq, soit dix. Remettre quinze tel quel garderait le bon chemin mais annoncerait un numéro qui n'est plus celui de cette fiche. À l'inverse, chercher physiquement dix sans traduire la demande choisirait l'ancienne feuille huit, désormais treize, avec un résultat affiché sept ; la fiche dix disponible possède zéro et la bat. Camille inscrit donc deux conversions distinctes, avant la recherche et après la feuille trouvée.
La transformation est une bijection sur les seize numéros : appliquer deux fois cinq rend le numéro initial. Elle conserve ainsi le nombre d'exemplaires de chaque fiche et permet de retrouver son ancienne place depuis son nouvel affichage. Elle ne conserve pas leur ordre numérique. Dans cette branche, la liste affichée rangée est un, quatre, neuf, dix, treize, treize, au lieu de prendre la colonne ancienne un, quatre, huit, huit, douze, quinze dans cet ordre. Nora ne transporte donc pas les anciennes positions d'une liste numérique triée sous les seules nouvelles étiquettes. La recherche XOR traduite n'avait besoin que des branches physiques et de leurs effectifs.
Pour retirer une fiche affichée treize, Camille calcule treize combiné avec cinq et obtient huit. Elle retire un exemplaire dans la feuille physique1000 et laisse l'autre. Pour insérer une fiche affichée six, elle calcule six combiné avec cinq, soit trois, et ajoute physiquement0011. La nouvelle demande affichée six devient elle aussi trois, trouve cette feuille et rend six avec zéro. Ajouter physiquement six aurait au contraire affiché trois. Les conversions s'appliquent donc aussi aux mutations de la liste ; elles ne sont pas une décoration de la réponse qui permettrait de laisser les insertions dans un autre système de numéros.
Les deux fiches les plus proches peuvent être recherchées sans choisir une demande extérieure
Nora revient à la liste initiale pour chercher deux fiches entre elles, sans numéro demandé. Les deux huit donnent zéro et suffisent à fermer le minimum. Les retraits changent réellement ce problème : après en avoir gardé un seul, les numéros différents sont un, quatre, huit, douze et quinze. Les combinaisons des voisins dans cet ordre sont cinq, douze, quatre et trois. Camille remet douze et quinze avec trois. Une recherche ne conservant que les numéros différents dès le début aurait annoncé trois trop tôt, omettant le zéro des deux exemplaires encore présents dans la première version.
Camille explique pourquoi les voisins numériques suffisent lorsque les numéros sont différents. Prenons a plus petit que b plus petit que c. À la place la plus haute où a et c diffèrent, a vaut zéro et c un ; b se trouve d'un des deux côtés. S'il reste du côté de a, leur combinaison vaut zéro à cette place et est strictement plus petite que celle de a et c. S'il reste du côté de c, le même raisonnement vaut pour b et c. Une paire séparée par un numéro intermédiaire ne peut donc battre toutes les paires internes. Sur la liste remplie, un et quinze donnent quatorze, alors que leurs voisins offrent déjà trois ; Camille n'a pas à appeler tous les couples équivalents à ces voisinages.
Cette dernière recherche donne une paire de fiches et non la réponse à dix. Douze et quinze réalisent trois entre eux, tandis que huit restait le meilleur partenaire de dix lorsqu'il était disponible. Camille remet les deux commandes sur des lignes séparées. La première fournit un partenaire d'un numéro reçu ; la seconde choisit simultanément les deux partenaires dans le stock actuel. Leurs combinaisons et leurs multiplicités restent attachées aux versions réellement utilisées, avec les retraits et l'étiquette commune dans leurs branches propres.
Les catégories consultées ne justifient aucune recherche ou transformation de numéros. La feuille conserve chaque liste, sa demande et les conversions effectivement appliquées.