Pour un jeu après dîner, Nora souhaite remettre quatre cartes dans un ordre croissant. Elle conserve toutes les cartes : aucune n’est rejetée au fil des présentations. Sa feuille doit annoncer les paires de places à comparer, avant de connaître leur contenu. Nous allons remplir cette feuille, puis la modifier lorsque seules les places voisines peuvent être comparées ou lorsque les valeurs deviennent égales. Ces changements ne demandent pas tous la même correction.
Les cartes, leurs valeurs et les manipulations sont entièrement créées. Quatre places numérotées de gauche à droite reçoivent chacune une carte. Une comparaison entre deux places met la plus petite valeur dans la place de plus petit numéro, la plus grande dans l’autre ; elle échange les cartes seulement si nécessaire. Les places comparées sont fixées par la feuille et désignent leur contenu actuel. Aucun jeu réel, temps d’exécution, capacité d’attention ou préférence de convive n’est mesuré. Nous utilisons un modèle classique de comparaisons et d’échanges, sans invention revendiquée.
moses. présente des jeux.
Schmidt Spiele présente des jeux.
SmartGames présente des jeux.
Ces pages ont été lues textuellement pour leurs seules catégories. Aucun jeu nommé, règle de fabricant ou bénéfice annoncé n’est repris. Les comparaisons suivantes sont données par notre atelier sur papier et vérifiées dans leurs cas finis. Nous n’avons inspecté aucune image, carte commerciale ou dispositif capable de manipuler deux paires en même temps.
Fixer les paires qui acheminent les deux extrêmes
Le premier jeu contient quatre valeurs distinctes. Nora choisit cinq comparaisons, dans cet ordre : places un et deux ; trois et quatre ; un et trois ; deux et quatre ; enfin deux et trois. Ces numéros restent des places, même après un échange. Nous cherchons un classement complet au terme de cette suite, pas seulement la plus petite ou la plus grande carte. Pour lire ce résultat, il est utile de distinguer ce que les quatre premières comparaisons établissent de ce qui manque encore au milieu.
Après les comparaisons un-deux et trois-quatre, appelons a et b les valeurs du premier couple, c et d celles du second. Nous savons que a est inférieur à b et c inférieur à d. La plus petite des quatre valeurs doit donc être a ou c : b a déjà une valeur plus petite qu’elle dans son couple, et d aussi. La comparaison un-trois place le plus petit de a et c en première position. Elle garantit ainsi le minimum de tout le groupe, sans qu’il ait fallu comparer cette carte directement à chacune des trois autres.
La plus grande valeur doit être b ou d, puisque a et c ont chacune une valeur plus grande dans leur couple. La comparaison deux-quatre place le plus grand de b et d en quatrième position. Elle ne touche pas aux places un et trois qui viennent de traiter a et c. Le minimum demeure donc en première place et le maximum rejoint la dernière. Nora conserve ces deux conséquences avec les paires qu’elle a choisies. Dire que les quatre comparaisons ont « rapproché les cartes de leur ordre » serait moins précis que ces deux extrêmes désormais établis.
Les valeurs restant aux places deux et trois sont le plus petit de b et d et le plus grand de a et c. Elles ne sont pas nécessairement dans le bon ordre entre elles. Avec les valeurs initiales deux, quatre, un, trois, les deux premières comparaisons ne font aucun échange. Un-trois donne un, quatre, deux, trois ; deux-quatre donne un, trois, deux, quatre. Les extrêmes sont corrects, mais trois précède encore deux. Nora refuse donc la feuille raccourcie à quatre comparaisons. Elle conserve la dernière comparaison deux-trois, qui donne un, deux, trois, quatre dans ce cas.
Cette dernière comparaison suffit également pour les autres entrées distinctes. Les extrêmes sont déjà à leurs places finales, et les deux valeurs restantes n’ont plus qu’à être ordonnées entre elles. Nora peut donc remettre la suite entière de cinq paires. Dans notre vérification séparée, les vingt-quatre permutations de quatre rangs distincts donnent toutes l’ordre croissant au terme de cette suite. Le raisonnement par couples explique toutefois ce résultat sans attribuer à chaque entrée un choix de paires différent : la feuille garde les mêmes cinq lignes pour toutes.
Une comparaison peut être nécessaire sans provoquer un échange
Nora remplit la suite sur l’entrée quatre, trois, deux, un. Un-deux donne trois, quatre, deux, un. Trois-quatre donne trois, quatre, un, deux. Un-trois donne un, quatre, trois, deux. Deux-quatre donne un, deux, trois, quatre. La dernière comparaison deux-trois est effectuée, mais n’échange rien. Nous avons donc cinq comparaisons et quatre échanges dans cette réalisation. Nora retire la mention « cinq échanges » de sa feuille de résultat ; les paires annoncées ne décrivaient pas cinq déplacements obligatoires.
L’absence du dernier échange sur cette entrée ne lui permet pas de supprimer la dernière comparaison pour les autres. L’entrée deux-quatre-un-trois avait montré précisément l’inversion que les quatre premières laissaient au milieu. Nora conserve donc deux traces distinctes : le projet possède cinq paires fixes, la réalisation sur quatre-trois-deux-un comporte quatre échanges. Cette branche ne cherche pas à justifier une comparaison vide pour rallonger le jeu. Elle vérifie que la dernière paire peut ne rien déplacer dans un cas, tout en étant indispensable à la promesse commune de classement.
Nous posons aussi une limite simple pour les entrées distinctes. Une procédure fondée uniquement sur des comparaisons binaires doit distinguer vingt-quatre ordres relatifs initiaux pour garantir leur classement. Quatre comparaisons offrent au plus seize suites de résultats. Dans une même suite, les mêmes échanges de positions seraient exécutés et ne pourraient ranger deux ordres relatifs différents en un ordre strict croissant. Quatre ne suffisent donc pas ; la suite de Nora atteint la borne de cinq. Ce contrôle de capacité reste bref : il ne décrit ni la durée d’une manipulation ni une garantie sur des valeurs dont les comparaisons seraient imparfaites.
Regrouper deux comparaisons ne permet pas de partager une place
Nora souhaite maintenant présenter la feuille par étapes, chacune utilisant plusieurs paires disjointes. Notre modèle autorise que toutes les paires d’une étape utilisent le contenu présent à son début, puis donnent ensemble leurs résultats. Une place ne peut appartenir qu’à une paire dans cette étape. Nous ne supposons pas deux personnes ou deux appareils réels ; les étapes servent seulement à décrire quelles comparaisons peuvent être groupées sans se disputer une carte.
La première étape regroupe un-deux et trois-quatre. Ces deux couples n’ont aucune place commune ; le résultat de l’un ne change pas les cartes que l’autre compare. La deuxième regroupe un-trois et deux-quatre, également disjoints. La troisième garde deux-trois seul. Nous retrouvons ainsi les cinq comparaisons en trois étapes. Dans chacune des deux premières, commencer par l’une ou par l’autre des paires donnerait le même état final, puisqu’aucune ne lit ou ne modifie les places de sa voisine. Nora inscrit ces groupes au lieu de présenter cinq étapes obligatoires.
Deux comparaisons partageant une place ne possèdent pas cette liberté. Avec trois valeurs trois, deux, un aux places un, deux, trois, la comparaison un-deux demanderait de placer trois en deuxième position, tandis que deux-trois demanderait d’y placer un si toutes deux lisaient le même état initial. Ces deux résultats revendiquent la même place avec deux cartes différentes. Nora refuse de les déclarer une étape simultanée. L’ordre doit être renseigné : un-deux puis deux-trois donne deux, un, trois ; l’ordre inverse donne un, trois, deux. Aucun de ces deux états n’est inventé comme résultat commun aux deux ordres.
Pour notre suite complète, ce contrôle ne demande aucune comparaison supplémentaire. Il confirme seulement les deux groupes disjoints retenus. Deux étapes ne pourraient toutefois pas suffire à une suite fixe garantissant le classement de quatre valeurs distinctes : chaque étape accueille au maximum deux paires disjointes, soit quatre comparaisons en tout. La limite précédente en demandait au moins cinq. Les trois étapes de Nora atteignent donc aussi le minimum dans cette permission de groupement. Les deux minima ont des unités différentes, cinq comparaisons et trois étapes, même si la même feuille les atteint ici.
Limiter les comparaisons aux places voisines change la feuille
Une nouvelle version interdit un-trois et deux-quatre. Seules un-deux, deux-trois et trois-quatre sont permises. Nora ne remplace pas les paires interdites par un échange de cartes arbitraire qui ferait revenir silencieusement l’ancienne permission. Elle construit une feuille différente : première étape un-deux avec trois-quatre ; deuxième deux-trois ; troisième un-deux avec trois-quatre ; quatrième deux-trois. Elle a désormais six comparaisons en quatre étapes.
Reprenons a inférieur à b et c inférieur à d après la première étape. La deuxième compare b et c au milieu. L’état devient a, le plus petit de b et c, le plus grand de b et c, d. Dans la troisième étape, un-deux place en première position le minimum de a, b et c. Comme a est déjà inférieur à b et c inférieur à d, ce minimum est celui des quatre valeurs. Trois-quatre place à la fin le maximum de b, c et d ; puisque b dépasse a, c’est également le maximum des quatre. Les deux places intermédiaires restent à comparer, ce que fait la quatrième étape.
Cette deuxième feuille classe donc toutes les entrées distinctes avec les paires désormais autorisées. Nora la vérifie également sur les vingt-quatre ordres, sans emprunter les deux comparaisons à distance de l’ancienne feuille. Sur quatre, trois, deux, un, la première étape donne trois, quatre, un, deux ; la deuxième trois, un, quatre, deux ; la troisième un, trois, deux, quatre ; la quatrième un, deux, trois, quatre. Les six comparaisons y provoquent chacune un échange. La permission limitée aux voisins ne retrouve pas la même quantité de travail que les cinq paires de la première version.
Le nombre six est nécessaire dans cette version. Au départ de cette entrée inversée, chacune des six paires de cartes distinctes se présente dans l’ordre contraire au classement final. Un échange entre places voisines ne change que l’ordre relatif des deux cartes échangées : aucune troisième carte n’est franchie. Chaque échange corrige donc une seule de ces six inversions. Il faut au moins six échanges voisins pour cette entrée, et donc au moins six comparaisons. Nora ne conserve pas la borne de cinq comme quantité suffisante sous la permission plus étroite, même si quatre cartes restent à classer.
Trois étapes voisines ne suffiraient pas non plus. Si une étape comporte deux paires disjointes, elles sont nécessairement un-deux et trois-quatre. Si chacune des trois étapes utilisait seulement ces deux paires, aucune carte ne franchirait la frontière entre les places deux et trois ; une entrée répartissant les petites valeurs à droite ne serait pas classée. Il faut donc une étape comportant deux-trois, qui ne peut recevoir aucune autre paire voisine disjointe. Les trois étapes auraient alors au plus deux plus un plus deux comparaisons, soit cinq, insuffisant pour les six inversions de l’entrée contraire. Nora retient les quatre étapes effectivement remplies.
Ne pas échanger directement deux égales ne conserve pas toujours leur ordre
Une autre version autorise à nouveau les comparaisons à distance, mais certaines valeurs sont égales. Chaque carte possède maintenant une identité distincte. Nora demande un ordre croissant des valeurs et, entre deux cartes égales, le maintien de leur ordre d’entrée. Nous donnons A, B, C, D dans cet ordre initial, avec les valeurs un, un, zéro, un. A doit donc précéder B, puis D parmi les trois cartes de valeur un. La carte C doit venir avant elles toutes pour le classement des valeurs.
Nora utilise d’abord la feuille de cinq comparaisons avec la consigne de ne pas échanger deux valeurs égales. Un-deux conserve A puis B ; trois-quatre conserve C puis D. Un-trois échange A et C : l’état devient C, B, A, D. Deux-quatre compare B et D, tous deux de valeur un, sans échange. Deux-trois compare ensuite B et A, encore égaux, et ne les échange pas davantage. Le résultat C, B, A, D classe bien les valeurs, mais inverse A et B. Nora refuse donc de qualifier cette consigne de maintien de l’ordre des égalités.
La cause est localisée dans l’échange à distance. Lorsque A est allé de la première à la troisième place, il a franchi B, qui est resté en deuxième. Les deux cartes égales ne se sont jamais trouvées dans une comparaison ayant ordonné leur échange. Cela n’a pourtant pas empêché leur ordre relatif de changer. Nora retire donc l’argument « aucune comparaison d’égales n’a provoqué d’échange ». Il décrit les décisions de ces paires, mais ne protège pas les cartes franchies entre les deux extrémités d’un échange. La propriété demandée porte sur le résultat des identités, pas seulement sur les valeurs testées directement.
Elle ajoute alors une seconde information au critère de comparaison : le numéro d’entrée original de la carte, utilisé seulement lorsque deux valeurs sont égales. A possède un, B deux, C trois, D quatre pour ce second critère. Chaque comparaison met d’abord la plus petite valeur avant l’autre ; à valeur égale, elle met d’abord le plus petit numéro original. Ce numéro voyage avec la carte et ne devient pas son numéro de place actuel après un échange. Les quatre clés ainsi formées sont distinctes, ce qui permet à la feuille initiale de cinq paires de les classer complètement.
Dans la même entrée, un-trois donne encore C, B, A, D. Deux-quatre conserve B avant D, puisque leurs numéros originaux sont deux et quatre. La dernière comparaison deux-trois échange cette fois B et A : leurs valeurs sont égales, mais le numéro un de A précède le numéro deux de B. Nora reçoit C, A, B, D, le résultat demandé. Le nouvel échange entre valeurs égales répare précisément l’ordre que le déplacement à distance avait modifié. La fiche conserve donc cinq comparaisons, mais leur donne un critère plus riche ; elle ne prétend pas que la première consigne avait déjà fourni ce résultat.
La garantie ne dépend pas seulement de cette entrée. Pour chaque groupe de valeurs égales, l’ordre croissant de leurs numéros originaux est exactement l’ordre demandé. Entre groupes de valeurs différentes, le premier critère garde la priorité. Classer ces clés distinctes met donc toutes les cartes en ordre croissant et ordonne chaque groupe égal comme à son entrée. Notre vérification sur les quatre-vingt-une suites de quatre valeurs choisies parmi zéro, un et deux conserve ce résultat avec les numéros originaux attachés aux cartes. Sans ce second critère, vingt de ces suites perdent au moins un ordre d’identités égales avec la feuille à distance.
Garder seulement les valeurs avec les paires voisines
Une dernière demande refuse ce second critère et n’autorise que les comparaisons de valeurs, sans échange lorsque celles-ci sont égales. Nora retient alors la feuille voisine de six comparaisons en quatre étapes. Un échange entre places voisines ne peut inverser deux identités égales sans les faire passer directement l’une devant l’autre. Or la consigne exclut précisément cet échange quand leurs valeurs sont égales. Les échanges d’autres cartes peuvent les déplacer, mais ne leur permettent pas de se franchir indirectement par un saut au-dessus d’une place intermédiaire.
Sur A un, B un, C zéro, D un, la première étape ne déplace rien. Deux-trois échange B et C, donnant A, C, B, D. La troisième étape échange A et C dans un-deux et conserve B devant D dans trois-quatre : nous avons C, A, B, D. La dernière comparaison deux-trois conserve A devant B. Cette fiche donne donc le résultat demandé avec les seules valeurs, en acceptant une comparaison de plus et une étape de plus que la feuille à clés enrichies. Nous avons aussi vérifié le maintien des identités égales sur les quatre-vingt-une suites de valeurs du même contrôle fini.
Nora garde les deux réponses possibles à la dernière comparaison : cinq paires à distance avec le numéro d’entrée comme second critère, ou six paires voisines avec les seules valeurs. Elles donnent le classement demandé sans réclamer la même information ni la même permission de déplacement. Pour la feuille finalement choisie, elle retient les paires voisines et conserve les identités sur ses cartes. Le résultat ne désigne pas un matériel plus rapide ou un jeu préférable auprès d’invités réels. Il ferme seulement une préparation remplie, avec ses paires, ses étapes et le sens exact de l’égalité qu’elle voulait maintenir.