GameTheory 20c : Le chemin minimal sur un second substrat — jeux ordinaux 3×2, murs traversables et raccourcis
Opération 13 « Traverser un mur » de l’EPIC #12204 (Chantier 1 — la table des opérations). Seconde attestation, second substrat : la première (GameTheory-20 et 20b, ex-24/24b) vivait sur les jeux 2×2 ordinaux de Robinson-Goforth ; celle-ci monte au substrat 3×2 ordinal — chaque joueur range 6 cases, l’univers des chambres strictes passe de 24×24 = 576 à 720×720 = 518 400 jeux.
La question falsifiable que ce notebook pose. Sur 2×2, GT-20 a mesuré que traverser les murs (passer par des ex æquo) ne raccourcit jamais un chemin minimal entre chambres : 0 raccourci sur 576 paires. Ce verdict survive-t-il au changement de substrat ? La réponse mesurée ici est non : sur 3×2, 77 760 paires sur 518 400 (15,0 %) raccourcissent en traversant les murs, et le diamètre par côté se contracte de 15 à 10. La stratification qui ne comprimait pas la métrique à 2×2 devient une compression métrique à 3×2.
La loi que ce notebook met à l’épreuve — Loi II du deuxième voyage de digestion ICT :
recoordonner + passer du vérificateur au constructeur : le précédent important n’est pas seulement le changement de coordonnées ; c’est changement de coordonnées plus passage du vérificateur au constructeur.
Comme GT-20, chaque témoin est produit par un constructeur (BFS + remontée des parents) puis certifié par un vérificateur séparé qui ne réutilise rien : il re-dérive l’adjacence par son propre code et re-fait une recherche exhaustive pour la minimalité.
Plan. §1 les deux univers (ordres faibles, chambres) ; §2 les générateurs et les trois modèles de graphe ; §3 reproduction du verdict 2×2 sous modèle fermé ; §4 le recensement exhaustif 3×2 — la réfutation ; §5 le produit de jeux et son lemme de décomposition ; §6 le constructeur et le vérificateur séparés (Loi II), y compris le chemin de l’antipode à travers les murs ; §7 le contrôle négatif ; §8 les géodésiques ; §9 trois exercices.
# === Configuration : GameTheory 20c, chemin minimal 3x2 ordinal - seconde attestation de l'operation 13 ===import timefrom itertools import product, combinationsfrom collections import dequeprint("GameTheory 20c : chemin minimal sur jeux ordinaux 3x2 (seconde attestation, operation 13)")print("Representation : jeu = (table_ligne, table_colonne), chaque table range 6 cases, rangs {1..6}")print("Convention GT-20 conservee : le rang 6 est le MEILLEUR resultat possible")print("Loi II : le constructeur PRODUIT le chemin, le verificateur separe le CERTIFIE par re-derivation")
GameTheory 20c : chemin minimal sur jeux ordinaux 3x2 (seconde attestation, operation 13)
Representation : jeu = (table_ligne, table_colonne), chaque table range 6 cases, rangs {1..6}
Convention GT-20 conservee : le rang 6 est le MEILLEUR resultat possible
Loi II : le constructeur PRODUIT le chemin, le verificateur separe le CERTIFIE par re-derivation
Lecture du résultat — le changement d’échelle comme variable expérimentale : un seul paramètre change
Le changement d’échelle est la variable expérimentale : GT-20 étudiait des tables 2×2 (4 cases par joueur), ici chaque joueur ordinal dispose d’une table 3×2 — 6 cases à ranger. Toute la machinerie conceptuelle (chambres strictes, murs d’ex æquo, facettes) est portée telle quelle ; c’est précisément ce qui rend la comparaison falsifiable : un seul paramètre change, le substrat. La convention des rangs suit GT-20 (6 = meilleur), et la Loi II structure tout le notebook : aucun témoin n’est accepté sur la parole du code qui l’a produit.
# === Section 1.1 : enumeration des ordres faibles sur 6 cases (et rappel 4 cases) ===def canonique(t):"""Cle canonique d'un uplet : relabelage croissant des valeurs distinctes (GT-20, portee tel quel).""" vals =sorted(set(t))returntuple(vals.index(v) +1for v in t)def ordres_faibles(n):# Tous les rangements faibles (avec ex aequo) de n cases, formes canoniques.returnsorted({canonique(t) for t in product(range(1, n +1), repeat=n)})OF4 = ordres_faibles(4)ST4 = [t for t in OF4 iflen(set(t)) ==4]OF6 = ordres_faibles(6)ST6 = [t for t in OF6 iflen(set(t)) ==6]print("Substrat 2x2 (GT-20) : ordres faibles =", len(OF4), "(nombre de Fubini F4)","| stricts =", len(ST4), "| chambres =", len(ST4) **2)print("Substrat 3x2 (ici) : ordres faibles =", len(OF6), "(nombre de Fubini F6)","| stricts =", len(ST6), "| chambres =", len(ST6) **2)print("Avec ex aequo 3x2 :", len(OF6) -len(ST6), "tables liees -- les futures faces des murs")
Substrat 2x2 (GT-20) : ordres faibles = 75 (nombre de Fubini F4) | stricts = 24 | chambres = 576
Substrat 3x2 (ici) : ordres faibles = 4683 (nombre de Fubini F6) | stricts = 720 | chambres = 518400
Avec ex aequo 3x2 : 3963 tables liees -- les futures faces des murs
Lecture du résultat — les nombres de Fubini : 720 tables strictes, 4 683 ordres faibles, 518 400 chambres
Les nombres de Fubini comptent les ordres faibles : F4 = 75, F6 = 4 683. Le côté 3×2 porte donc 720 ordres stricts (= 6!) et 4 683 ordres faibles, contre 24 (= 4!) et 75 pour le 2×2. Le produit des deux joueurs donne l’univers des jeux : 518 400 chambres strictes en 3×2, 21 930 489 jeux au total si l’on admet les murs des deux côtés à la fois — un univers que nous ne parcourrons pas exhaustivement au niveau jeu (voir le lemme du §5, qui le couvre par décomposition). L’explosion combinatoire est le prix du changement de substrat ; elle est aussi ce qui rend la question des raccourcis non triviale.
# === Section 1.2 : les jeux canoniques 3x2 (convention GT-21 / GT-3b / GT-20 etendue) ===def afficher_jeu(nom, jeu): row, col = jeuprint(nom)for i inrange(3):print(f" Ligne | {row[2* i]:>2}{row[2* i +1]:<2}| Colonne | {col[2* i]:>2}{col[2* i +1]:<2}|")return jeuIDENTITE = ((1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6)) # les deux joueurs preferent la meme caseRENVERSE = ((6, 5, 4, 3, 2, 1), (6, 5, 4, 3, 2, 1)) # les deux antipodes du permutoedre S6ROTATION = ((3, 4, 5, 6, 1, 2), (5, 6, 1, 2, 3, 4)) # conflit pur : chaque meilleure case d'un joueurMUR_PARTIEL = ((1, 2, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6)) # Ligne indifferente entre ses cases 2 et 3for nom, j in [("Identite", IDENTITE), ("Renversement", RENVERSE), ("Rotation", ROTATION), ("Mur partiel (Ligne indifferente 2~3)", MUR_PARTIEL)]: afficher_jeu(nom, j) strict =all(len(set(t)) ==6for t in j)print(" strict (chambre) :", strict, "| mur :", not strict)print()
Lecture du résultat — les jeux canoniques : deux antipodes, un conflit d’intérêts, et MUR_PARTIEL hors des chambres
L’Identite et le Renversement sont les deux antipodes du permutoèdre S6 × S6 : leur distance par côté est le diamètre (§2.2). ROTATION donne un exemple de conflit d’intérêts ordinal pur — les meilleures cases des deux joueurs diffèrent. MUR_PARTIEL n’est pas une chambre : la table de Ligne porte un ex æquo (deux cases au rang 2), c’est un point de l’univers étendu, une face du mur. La question de l’opération 13 est exactement : que se passe-t-il quand un chemin traverse de telles faces ?
Un mot sur ce que « jeu ordinal 3×2 » veut dire ici, pour éviter tout malentendu de modélisation. Chaque joueur range les six cases de la matrice 3 lignes × 2 colonnes par ordre de préférence, sans intensité cardinale : seuls les rangs comptent, exactement comme dans le 2×2 de Robinson-Goforth porté par GT-20/GT-3b. Les 720 tables strictes par côté sont les 6! ordres totaux possibles ; une table avec ex æquo est un ordre partiel au sens où plusieurs cases partagent un rang. Aucune théorie des équilibres n’est mobilisée dans ce notebook : l’objet d’étude est la géométrie de l’espace des préférences — la question de l’opération 13 est une question de métrique sur cet espace, pas de comportement stratégique.
# === Section 2.1 : les generateurs -- swap de facettes, fusion (descente de mur), scission (remontee) ===def swap_adjacent(t, k):"""Traversee de facette k<->k+1 : echange les cases portant les valeurs k et k+1 (tables strictes).""" pk, pk1 = t.index(k), t.index(k +1) l =list(t) l[pk], l[pk1] = l[pk1], l[pk]returntuple(l)def fusion(t, k):"""Descente de mur (le faire_le_tie de GT-20) : coalesce les valeurs k et k+1, forme canonique."""return canonique(tuple(k if v == k +1else v for v in t))def scissions(t):"""Remontee de mur : chaque bipartition non triviale d'un bloc d'ex aequo, dans les deux ordres.""" res = []for v insorted(set(t)): P = [i for i, x inenumerate(t) if x == v] m =len(P)if m <2:continuefor j inrange(1, m):for S in combinations(P, j): s =set(S) res.append(canonique(tuple( (v +1if x == v and i notin s else (v if x == v else (x +1if x > v else x)))for i, x inenumerate(t))))return rest = (1, 2, 3, 4, 5, 6)print("Table identite :", t)print("swap facette 2<->3 :", swap_adjacent(t, 2))print("fusion 2~3 (descente de mur) :", fusion(t, 2))print("scissions de la table liee (1,2,2,3,4,5) :", scissions((1, 2, 2, 3, 4, 5)))print("Le swap de singletons = fusion puis scission dans l'autre sens :", swap_adjacent(t, 2) in scissions(fusion(t, 2)))
Table identite : (1, 2, 3, 4, 5, 6)
swap facette 2<->3 : (1, 3, 2, 4, 5, 6)
fusion 2~3 (descente de mur) : (1, 2, 2, 3, 4, 5)
scissions de la table liee (1,2,2,3,4,5) : [(1, 2, 3, 4, 5, 6), (1, 3, 2, 4, 5, 6)]
Le swap de singletons = fusion puis scission dans l'autre sens : True
Lecture du résultat — trois familles de générateurs, et le swap décomposé en fusion puis scission
Trois familles de générateurs, et une identité structurelle qui éclaire tout le notebook : un swap de facettes entre deux valeurs strictes est exactement une fusion suivie d’une scission dans l’ordre opposé (vérifié ci-dessus). Autrement dit, le permutoèdre des chambres est plongé dans le graphe des ordres faibles : chaque arête de chambre se décompose en deux pas de mur. C’est cette décomposition qui rend la question des raccourcis sensée — traverser les murs coûte des pas supplémentaires pour réordonner, mais permet de déplacer des blocs entiers en une seule scission. Le verdict 2×2 de GT-20 disait que ce troc n’était jamais rentable à 4 cases ; le §4 mesure s’il le reste à 6.
Les trois modèles de graphe utilisés dans la suite (déclarés ici, utilisés ensuite) :
Modèle
Sommets
Arêtes
Question
Chambres (permutoèdre)
ordres stricts
swaps de facettes
distance de référence d_perm
Murs dirigés (GT-20 historique)
ordres faibles
swaps + fusions à sens unique
reproduction du cadre original
Treillis fermé (canonique)
ordres faibles
fusions + scissions, non dirigé
un mur se traverse dans les deux sens
Le modèle fermé est celui du graphe de couverture du treillis des ordres faibles — l’objet standard de la combinatoire des arrangements de type A. Il est le seul où « traverser un mur » a un sens honnête : descendre une facette et pouvoir remonter ailleurs. C’est lui qui porte la question falsifiable.
Pourquoi ce choix canonique plutôt qu’un autre ? Une modélisation naïve du modèle fermé consisterait à garder les swaps aussi sur les tables liées — mais un swap entre deux valeurs liées n’a pas de définition naturelle (échanger quelles occurrences ?), et l’échange de blocs entiers déplace plusieurs cases pour un pas, ce qui fabrique des raccourcis par fiat de modélisation plutôt que par la structure. En restant sur les seules relations de couverture du treillis — fusionner deux blocs adjacents, ou scinder un bloc — chaque pas a exactement une signification : on descend dans la stratification (on renonce à départager deux cases) ou on remonte (on les départage autrement). La question « les murs raccourcissent-ils ? » devient alors une question sur l’objet mathématique standard, pas sur les détails d’une implémentation.
# === Section 2.2 : construction des adjacences, symetrie, connectivite, diametres mesures ===def voisins_permutoedre(t, n):return [swap_adjacent(t, k) for k inrange(1, n)]def voisins_treillis(t, n):"""Fusions (k et k+1 valeurs presentes) + scissions -- le graphe de couverture du treillis.""" res = [] vals =set(t)for k inrange(1, n):if k in vals and k +1in vals: res.append(fusion(t, k)) res.extend(scissions(t))return resdef bfs(src, adj):"""BFS exhaustive ; adj est un dictionnaire sommet -> voisinage (le constructeur l'utilisera aussi).""" dist = {src: 0} q = deque([src])while q: u = q.popleft()for v in adj[u]:if v notin dist: dist[v] = dist[u] +1 q.append(v)return distgraphs = {}for n, OF, ST in ((4, OF4, ST4), (6, OF6, ST6)): adjP = {t: tuple(voisins_permutoedre(t, n)) for t in ST} adjC = {t: tuple(voisins_treillis(t, n)) for t in OF} asym =sum(1for u, vs in adjC.items() for v in vs if u notin adjC[v]) deg_moy =sum(len(v) for v in adjC.values()) /len(adjC) dP = bfs(ST[0], adjP) dC = bfs(OF[0], adjC) graphs[n] = (adjP, adjC)print(f"n={n} | stricts={len(ST)} faibles={len(OF)} | treillis : asymetries={asym}, "f"degre moyen={deg_moy:.1f}, connexe={len(dC)}/{len(OF)}, "f"excentricite du centre tout-lie={max(dC.values())} -> diametre = {2*max(dC.values())}")print(f" | permutoedre : connexe={len(dP)}/{len(ST)}, diametre={max(dP.values())} "f"(= inversions de l'element le plus long w0 : {n * (n -1) //2})")
n=4 | stricts=24 faibles=75 | treillis : asymetries=0, degre moyen=4.2, connexe=75/75, excentricite du centre tout-lie=3 -> diametre = 6
| permutoedre : connexe=24/24, diametre=6 (= inversions de l'element le plus long w0 : 6)
n=6 | stricts=720 faibles=4683 | treillis : asymetries=0, degre moyen=7.1, connexe=4683/4683, excentricite du centre tout-lie=5 -> diametre = 10
| permutoedre : connexe=720/720, diametre=15 (= inversions de l'element le plus long w0 : 15)
Lecture du résultat — les diamètres mesurés : 6 et 15 sur le permutoèdre, 6 et 10 sur le treillis
Deux contrôles structurels passent : le graphe du treillis est exactement symétrique (0 asymétrie — la remontée de mur est bien l’inverse de la descente), et les diamètres mesurés du permutoèdre valent 6 (n=4) et 15 (n=6), soit les nombres d’inversions de l’élément le plus long w0 de S4 et S6 — la théorie des groupes de Coxeter prédit ces valeurs et la mesure les confirme.
Pour le treillis, la mesure directe donne l’excentricité de la table tout-liée : 3 (n=4) et 5 (n=6). Ce n’est pas le diamètre, mais presque : la table tout-liée est le centre du treillis — atteindre une table à r blocs depuis elle demande exactement r−1 scissions, une par bloc créé — donc toute paire de sommets est à au plus 2×(n−1) l’un de l’autre en passant par le centre. Le diamètre du treillis vaut ainsi 6 (n=4) et 10 (n=6), et la borne est serrée : le §6 la réalise entre les deux antipodes stricts, certifié par le vérificateur. Premier fait saillant déjà visible à n=6 : 10 < 15 — la contraction métrique existe dans l’univers étendu ; reste à savoir si elle touche les paires de chambres (le §4 y répond). À n=4 en revanche, 6 = 6 : premier indice que le 2×2 n’a pas de marge.
# === Section 3 : reproduction du verdict 2x2 de GT-20 sous le modele ferme ===# GT-20 avait mesure 0 raccourci sur les 576 paires de chambres 2x2, mais avec des murs a sens# unique (swaps + faire_le_tie diriges) : une fois un mur descendu, impossible de remonter, donc# le 0 etait en partie structurel. On re-meure ici sous le modele ferme (fusions + scissions).def recensement(n, ST, adjP, adjC):"""Pour chaque paire ordonnee de chambres : d_treillis < d_permutoedre ?""" raccourcis = egal = paires =0 exemple =Nonefor a in ST: dperm = bfs(a, adjP) dtl = bfs(a, adjC)for b in ST: paires +=1if dtl[b] < dperm[b]: raccourcis +=1if exemple isNoneand b > a: exemple = (a, b, dperm[b], dtl[b])elif dtl[b] == dperm[b]: egal +=1return paires, raccourcis, egal, exemplet0 = time.time()paires4, rc4, eg4, ex4 = recensement(4, ST4, *graphs[4])print(f"Recensement 2x2 (modele ferme) : {paires4} paires ordonnees")print(f" raccourcis (d_treillis < d_perm) : {rc4}")print(f" egalites (aucun gain a traverser) : {eg4}")print(f" exemple de raccourci : {ex4}")print(f" ({time.time() - t0:.1f}s)")
Recensement 2x2 (modele ferme) : 576 paires ordonnees
raccourcis (d_treillis < d_perm) : 0
egalites (aucun gain a traverser) : 48
exemple de raccourci : None
(0.0s)
Lecture du résultat — le verdict 2×2 survit au modèle fermé : 0 raccourci sur 576 paires
Le verdict de GT-20 survit au modèle fermé : 0 raccourci sur 576 paires, même quand les murs se traversent dans les deux sens. La mesure originale n’était donc pas un artefact du sens unique — à 4 cases, le troc « des pas supplémentaires pour réordonner » n’est jamais rentable, et les 48 égalités (dont l’antipode, 6 = 2×(4−1)) montrent que le meilleur chemin par les murs égale tout au plus le chemin de chambres. La généralisation à tester en §4 est ainsi proprement posée : le même banc, le même modèle fermé, un seul changement — le substrat.
Lecture du résultat — la généralisation est réfutée : 77 760 paires sur 518 400, diamètre contracté de 15 à 10
La généralisation est réfutée. Sur le substrat 3×2, 77 760 paires ordonnées de chambres sur 518 400 — 15,0 % — ont un chemin plus court en traversant les murs qu’en restant dans les chambres, et le diamètre par côté se contracte de 15 à 10. Le verdict 2×2 (« la stratification ne comprime pas la métrique ») n’était pas un théorème de l’opération : c’était une propriété du petit substrat.
Pourquoi 10, et pourquoi par là. Le chemin intégral par les murs — fusionner tout (5 fusions successives jusqu’à la table tout-liée), puis scissionner dans l’ordre cible (5 remontées) — coûte exactement 2×(6−1) = 10 : c’est lui qui réalise le nouveau diamètre entre antipodes, là où le permutoèdre en demande 15. L’économie vient des blocs : une seule scission d’un bloc de taille m replace m cases d’un coup, quand le permutoèdre doit les permuter une à une.
L’arithmétique du troc mérite d’être écrite noir sur blanc, car c’est elle qui explique la frontière 2×2 / 3×2. Toute traversée utile de mur coûte au moins 2 pas (une descente, une remontée) — pour rentabiliser, le déplacement de blocs réalisé entre les deux doit économiser au moins 2 swaps. Or échanger les positions de deux éléments séparés par j rangs coûte j swaps au permutoèdre, et une paire fusion/scission bien placée peut déplacer jusqu’à m−1 éléments d’un bloc de taille m. À 4 cases, les blocs disponibles (taille ≤ 4, mais après seulement 3 fusions) ne laissent aucune configuration où le troc gagne — le recensement du §3 le mesure : jamais. À 6 cases, la table tout-liée offre un bloc de taille 6 : une seule scission dans l’ordre inverse y déplace 5 éléments, économie brute de l’ordre de 10 swaps pour 2 pas de traversée — d’où le gain net de 5. La question de savoir si toutes les paires gagnent (non : 85 % des paires ne raccourcissent pas — et parmi elles, la majorité des trajets sont même plus longs par les murs) et de combien est précisément ce que le recensement mesure, et l’exercice 2 y revient par le bout des antipodes.
C’est exactement le type de résultat que la table des opérations #12204 veut pour l’opération 13 : non pas « on rejoue le témoin », mais le témoin produit une connaissance nouvelle sur la frontière de la loi — ici, la borne où « traverser un mur » cesse d’être métriquement neutre et devient un raccourci structurel.
# === Section 5 : le produit de jeux et son lemme de decomposition ===# Les generateurs ne touchent qu'un cote a la fois : le graphe de jeux est le produit cartesien# des deux graphes par cote. Lemme : d_jeu(G, H) = d_cote(row_G, row_H) + d_cote(col_G, col_H),# dans CHACUN des deux modeles (chambres et treillis). Verification directe sur l'antipode.def voisins_jeu_chambres(jeu, n=6):"""<= 10 voisins : 5 swaps par cote, calcules a la volee (pas d'enumeration prealable).""" row, col = jeu res = []for cote in (0, 1): t = jeu[cote]for k inrange(1, n): v = swap_adjacent(t, k) res.append((v, jeu[1]) if cote ==0else (jeu[0], v))return resdef bfs_jeu(src, voisins_fn): dist = {src: 0} q = deque([src])while q: u = q.popleft()for v in voisins_fn(u):if v notin dist: dist[v] = dist[u] +1 q.append(v)return distt0 = time.time()dist_jeu = bfs_jeu(IDENTITE, voisins_jeu_chambres)atteint =len(dist_jeu)d_directe = dist_jeu[RENVERSE]d_decomposee =15+15print(f"BFS directe sur le produit des 518 400 chambres : {atteint} jeux atteints depuis Identite")print(f"distance Identite -> Renversement : directe = {d_directe} | par decomposition = {d_decomposee}")print(f"concordance : {d_directe == d_decomposee} ({time.time() - t0:.1f}s)")
BFS directe sur le produit des 518 400 chambres : 518400 jeux atteints depuis Identite
distance Identite -> Renversement : directe = 30 | par decomposition = 30
concordance : True (2.9s)
Lecture du résultat — le lemme de décomposition contrôlé par BFS : 30 = 15 + 15
La BFS directe sur le produit des chambres (518 400 sommets, degré 10) confirme le lemme de décomposition : 30 = 15 + 15. Ce lemme est ce qui garde le substrat 3×2 tractable honnêtement : l’univers complet de jeux avec murs des deux côtés compte 4 683² ≈ 21,9 millions de sommets — on ne l’énumère pas, on le couvre : toute distance de jeu s’obtient en sommant deux distances de côté, dans les deux modèles. Le recensement du §4, exhaustif par côté, est donc exhaustif pour les jeux au sens du lemme. (La BFS produit ci-dessus n’est pas une preuve du lemme — elle en est un contrôle ; la preuve est l’argument : chaque pas touche un seul côté.)
Pourquoi garder ce contrôle coûteux alors que l’argument est simple ? Parce que le lemme porte tout le notebook : si l’entrelacement des générateurs cachait une subtilité — par exemple un swap simultané des deux côtés compté pour un pas, ou une interaction entre les murs de Ligne et ceux de Colonne —, toutes les distances de jeu dérivées du §4 seraient fausses sans aucun signal d’erreur local. Le contrôle direct sur l’antipode (le cas où l’erreur éventuelle serait maximale, 30 étant le diamètre) est le témoin qui aurait le contradire le premier. C’est la même discipline que le vérificateur du §6 : on ne croit pas un argument élégant sans un recalcul indépendant là où il est le plus vulnérable.
# === Section 6.1 : construire_chemin -- le constructeur temoin (portage GT-20) ===def construire_chemin(depart, arrivee, adj):"""Produit une suite (table, table) de depart a arrivee par BFS + remontee des parents.""" parent = {depart: None} q = deque([depart])while q: u = q.popleft()if u == arrivee:breakfor v in adj[u]:if v notin parent: parent[v] = u q.append(v)if arrivee notin parent:returnNone chaine = [] cur = arriveewhile parent[cur] isnotNone: chaine.append((parent[cur], cur)) cur = parent[cur] chaine.reverse()return chainechemin_perm = construire_chemin(IDENTITE[0], RENVERSE[0], graphs[6][0])print("Chemin de chambres Identite -> Renversement (cote Ligne) :", len(chemin_perm), "pas")for i, (a, b) inenumerate(chemin_perm[:5]):print(f" pas {i +1:>2} : {a} -> {b}")print(" ...")chemin_murs = construire_chemin(IDENTITE[0], RENVERSE[0], graphs[6][1])print("Chemin par les murs Identite -> Renversement (cote Ligne) :", len(chemin_murs), "pas")for i, (a, b) inenumerate(chemin_murs):print(f" pas {i +1:>2} : {a} -> {b}")
Lecture du résultat — le témoin de l’opération 13 : 15 pas par les chambres, 10 par les murs, 5 fusions puis 5 scissions
Le constructeur produit les deux témoins de côté : 15 pas par les chambres, 10 pas par les murs — et l’affichage du chemin de 10 pas révèle sa structure : les 5 premières étapes sont des fusions (la table se lie progressivement jusqu’à la table tout-liée (1, 1, 1, 1, 1, 1)), les 5 suivantes des scissions qui relâchent les blocs directement dans l’ordre renversé. Le chemin traverse la cellule centrale du treillis — le mur total — et c’est précisément cette traversée qui vaut 5 pas d’économie. C’est le témoin de l’opération 13 : un mur réellement traversé, dans les deux sens, produisant un gain mesuré.
# === Section 6.2 : verifier_chemin -- le verificateur independant (Loi II) ===# Le verificateur ne reutilise NI l'adjacence du constructeur, NI ses structures : il re-ecrit# ses propres predicats et refait une recherche exhaustive pour la preuve de minimalite.# Deux modeles, deux verificateurs, chacun re-derive du zero.def voisins_treillis_verif(t):"""Re-derivation independante du voisinage du treillis (code separe de la section 2.1).""" vals =sorted(set(t)) out = []for k inrange(1, 6):if k in vals and k +1in vals: merged = [k if v == k +1else v for v in t] rk =sorted(set(merged)) out.append(tuple(rk.index(v) +1for v in merged))for v in vals: pos = [i for i inrange(6) if t[i] == v]iflen(pos) <2:continuefor mask inrange(1, 2**len(pos) -1): bas = {pos[j] for j inrange(len(pos)) if mask >> j &1} nouv = []for i inrange(6):if i in bas: nouv.append(v)elif t[i] == v: nouv.append(v +1)else: x = t[i] nouv.append(x +1if x > v else x) rk =sorted(set(nouv)) out.append(tuple(rk.index(v) +1for v in nouv))return outdef voisins_perm_verif(t):"""Re-derivation independante du voisinage du permutoedre : echange des valeurs k, k+1.""" out = []for k inrange(1, 6): u = [v +1if v == k else (v -1if v == k +1else v) for v in t] out.append(tuple(u))return outdef _bfs_depart(src, voisins_fn): dist = {src: 0} q = deque([src])while q: u = q.popleft()for v in voisins_fn(u):if v notin dist: dist[v] = dist[u] +1 q.append(v)return distdef verdict_chemin(depart, arrivee, chaine, voisins_fn, nom_modele):"""Verdict independant : extremites, elementarite de chaque pas, minimalite exhaustive."""if chaine isNoneorlen(chaine) ==0:return"INVALIDE : chemin vide"if chaine[0][0] != depart or chaine[-1][1] != arrivee:return"INVALIDE : les extremites ne sont pas celles annoncees"for pred, cur in chaine:if cur notin voisins_fn(pred):returnf"INVALIDE : pas non elementaire {pred} -> {cur}" dist = _bfs_depart(depart, voisins_fn)iflen(chaine) != dist[arrivee]:returnf"INVALIDE : non minimal ({len(chaine)} pas, distance reelle {dist[arrivee]})"returnf"VALIDE [{nom_modele}] : {len(chaine)} pas, minimalite certifiee par recherche exhaustive independante"print("Chemin de chambres (15 pas) juge par le verificateur du permutoedre :")print(" ", verdict_chemin(IDENTITE[0], RENVERSE[0], chemin_perm, voisins_perm_verif, "permutoedre"))print("Chemin par les murs (10 pas) juge par le verificateur du treillis :")print(" ", verdict_chemin(IDENTITE[0], RENVERSE[0], chemin_murs, voisins_treillis_verif, "treillis"))
Chemin de chambres (15 pas) juge par le verificateur du permutoedre :
VALIDE [permutoedre] : 15 pas, minimalite certifiee par recherche exhaustive independante
Chemin par les murs (10 pas) juge par le verificateur du treillis :
VALIDE [treillis] : 10 pas, minimalite certifiee par recherche exhaustive independante
Lecture du résultat — deux minimalités dans deux graphes, certifiées par deux vérificateurs sans ligne commune
Chaque témoin est certifié dans son propre modèle, par un vérificateur qui ré-écrit tout : le chemin de 15 pas est validé élémentaire et minimal au sens des swaps (vérificateur du permutoèdre), le chemin de 10 pas au sens fusions/scissions (vérificateur du treillis) — comparez les deux implémentations de voisinage : elles ne partagent aucune ligne, c’est la séparation de la Loi II. Un point mérite d’être souligné : le chemin de chambres n’est pas un chemin du treillis — chacun de ses swaps s’y décompose en fusion + scission (§2.1). Les 15 et les 10 sont donc deux minimalités de deux graphes différents, et c’est précisément leur écart — 5 pas sur l’antipode — qui constitue la mesure de la contraction métrique du §4.
# === Section 7 : controle negatif -- le verificateur doit aussi savoir dire NON ===faux_compose = [(IDENTITE[0], swap_adjacent(swap_adjacent(IDENTITE[0], 1), 2)), (swap_adjacent(swap_adjacent(IDENTITE[0], 1), 2), RENVERSE[0])]faux_extremites = [(RENVERSE[0], swap_adjacent(RENVERSE[0], 1))]# Detour valide mais non minimal : le chemin de murs (10 pas) rallonge d'un aller-retour# sur le mur 5~6 (fusion puis scission retour), toujours elementaire -> 12 pas.x = fusion(IDENTITE[0], 5)chemin_detour = [(IDENTITE[0], x), (x, IDENTITE[0])] + chemin_mursprint("Controle 1 -- pas compose de deux swaps declare au verificateur du treillis :")print(" ", verdict_chemin(IDENTITE[0], RENVERSE[0], faux_compose, voisins_treillis_verif, "treillis"))print("Controle 2 -- extremites fausses :")print(" ", verdict_chemin(IDENTITE[0], RENVERSE[0], faux_extremites, voisins_perm_verif, "permutoedre"))print("Controle 3 -- detour de 12 pas (elementaire, extremites justes, non minimal) :")print(" ", verdict_chemin(IDENTITE[0], RENVERSE[0], chemin_detour, voisins_treillis_verif, "treillis"))
Controle 1 -- pas compose de deux swaps declare au verificateur du treillis :
INVALIDE : pas non elementaire (1, 2, 3, 4, 5, 6) -> (3, 1, 2, 4, 5, 6)
Controle 2 -- extremites fausses :
INVALIDE : les extremites ne sont pas celles annoncees
Controle 3 -- detour de 12 pas (elementaire, extremites justes, non minimal) :
INVALIDE : non minimal (12 pas, distance reelle 10)
Lecture du résultat — le contrôle négatif : trois modes de refus, dont un détour de 12 pas jugé non minimal
Un vérificateur qui ne saurait que dire VALIDE ne certifierait rien. Les trois contrôles exhibent trois modes de refus distincts : le pas composé de deux swaps est rejeté comme non élémentaire (aucun voisinage ne contient ce saut double), les extrémités fausses sont détectées avant toute recherche, et — le contrôle qui fait le travail — un détour parfaitement licite de 12 pas (fusion vers le mur 5~6 puis scission retour, insérée dans le vrai chemin de 10) est détecté non minimal. C’est lui qui prouve que la preuve de minimalité a les dents : elle ne se contente pas de valider la connectivité, elle distingue 12 de 10.
# === Section 8 : geometriques identite -> renversement sur le permutoedre S6 ===def compter_geodesiques(depart, arrivee, adj):"""Nombre de chemins minimaux : produits des chemins entrants, couche par couche (DAG des couches).""" dist = bfs(depart, adj) d = dist[arrivee] nb = {depart: 1}for couche inrange(1, d +1):for u, du in dist.items():if du == couche: nb[u] =sum(nb[v] for v in adj[u] if dist.get(v) == couche -1)return nb[arrivee]geo6 = compter_geodesiques(IDENTITE[0], RENVERSE[0], graphs[6][0])print("Geodesiques (1,2,3,4,5,6) -> (6,5,4,3,2,1) sur une table 3x2 :", geo6)print("Rappel GT-20 (S4, substrat 2x2) : 16 geodesiques pour l'antipode")
Geodesiques (1,2,3,4,5,6) -> (6,5,4,3,2,1) sur une table 3x2 : 292864
Rappel GT-20 (S4, substrat 2x2) : 16 geodesiques pour l'antipode
Lecture du résultat — 292 864 géodésiques au lieu de 16 : l’explosion du nombre de chemins minimaux
L’explosion du nombre de géodésiques (16 sur S4, 292 864 sur S6 — la valeur mesurée ci-dessus) matérialise la richesse du nouveau substrat : il n’existe pas un chemin minimal mais une famille entière, et le diamètre 15 n’est réalisé que par une fraction organisée des 720 tables. Ce comptage par DAG des couches est le même instrument que GT-20 (cross-check direct avec ses 16), porté à l’échelle supérieure sans changement de méthode — la reproductibilité de l’instrument à travers les substrats fait partie de l’attestation.
Le nombre de géodésiques dit aussi quelque chose de la robustesse du témoin du §6 : si l’antipode n’était atteint que par un unique chemin de 10 pas, on pourrait soupçonner une coincidence structurelle ; le fait qu’il existe par ailleurs des familles entières de chemins minimaux dans chaque modèle rappelle que la minimalité certifiée par le vérificateur porte sur la longueur, et que le constructeur n’en a extrait qu’un représentant. Un prolongement naturel (hors scope ici) serait de compter les géodésiques du trellis entre antipodes — la version « à travers les murs » de ce comptage — pour comparer les deux cardinaux.
# === Exercice 1 : chemin retour Renversement -> Identite, construit puis verifie independamment.# Etape 1 : chemin_retour = construire_chemin(RENVERSE[0], IDENTITE[0], graphs[6][1])# Etape 2 : verdict = verifier_chemin(RENVERSE[0], IDENTITE[0], chemin_retour)# Indice : le treillis est non dirige -- la longueur du retour doit egaler 10.chemin_retour =None# TODO etudiantverdict_retour =None# TODO etudiantprint("Exercice 1 : a completer (chemin retour Renversement -> Identite par les murs)")
Exercice 1 : a completer (chemin retour Renversement -> Identite par les murs)
Exercice 1 — Le chemin retour
Construisez le chemin de retour Renversement -> Identité sur le graphe du treillis, puis faites-le certifier par le vérificateur. Indice : le graphe est non dirigé, donc la longueur du retour est connue d’avance — c’est exactement ce que le vérificateur doit confirmer par sa propre recherche exhaustive.
# === Exercice 2 : les antipodes raccourcissent-ils tous ?# Etape 1 : dperm = bfs(IDENTITE[0], graphs[6][0]) ; antipodes = [t for t in ST6 if dperm[t] == 15]# Etape 2 : dtl = bfs(IDENTITE[0], graphs[6][1]) ; compter combien d'antipodes ont dtl[t] < 15.# Indice : le chemin tout-lie (5 fusions + 5 scissions = 10) n'est pas la seule facon de gagner.antipodes_raccourcis =None# TODO etudiantprint("Exercice 2 : a completer (combien des antipodes de distance 15 sont raccourcis par les murs)")
Exercice 2 : a completer (combien des antipodes de distance 15 sont raccourcis par les murs)
Exercice 2 — Le recensement des antipodes
Parmi les tables situées à la distance maximale 15 de l’identité dans le permutoèdre (les antipodes), combien sont raccourcies par les murs ? Indice : le chemin tout-lié en vaut 5 d’économie, mais certaines réorganisations partielles peuvent faire mieux ou moins bien — la distribution des gains est le sujet.
# Exercice 3 : traverser un mur triple.# Etape 1 : cible = canonique((2, 2, 2, 1, 3, 4)) # trois cases liees au rang 2# Etape 2 : chemin = construire_chemin(IDENTITE[0], cible, graphs[6][1])# Etape 3 : verdict = verifier_chemin(IDENTITE[0], cible, chemin)# Indice : combien de fusions pour lier trois cases, et la scission finale est-elle utile ici ?mur_triple =None# TODO etudiantprint("Exercice 3 : a completer (chemin minimal vers une table portant un ex aequo triple)")
Exercice 3 : a completer (chemin minimal vers une table portant un ex aequo triple)
Exercice 3 — Le mur triple
Construisez et certifiez un chemin minimal de l’identité vers une table portant un ex æquo triple. Indice : lier trois cases demande deux fusions ; demandez-vous si le vérificateur accepte un chemin qui re-descend scissionner quelque part — la réponse mesure la frontière entre réordonner par les murs et payer les allers-retours.
Conclusion — ce que cette seconde attestation établit
Pour la table des opérations #12204, opération 13 « Traverser un mur » : le témoin GT-20 (2×2) n’était pas isolé dans son genre — sa méthode (constructeur/vérificateur séparés, recensement exhaustif, contrôle négatif) se transpose à un second substrat, et c’est précisément cette transplantation qui produit la connaissance :
Le verdict 2×2 est robuste au modèle fermé : 0 raccourci sur 576 paires, murs traversables dans les deux sens (§3). La mesure GT-20 n’était pas un artefact du sens unique.
Le verdict ne survit pas au substrat 3×2 : 77 760 raccourcis sur 518 400 paires (15,0 %), diamètre par côté contracté de 15 à 10 (§4). Traverser les murs y est un raccourci structurel — porté par les scissions de blocs — et non une curiosité marginale.
Le témoin est certifié : chemin de l’antipode à travers le mur total (5 fusions + 5 scissions), construit puis validé par un vérificateur qui re-dérive tout (§6), contrôle négatif à l’appui (§7).
Résiduel assumé. L’univers complet de jeux avec murs bilatéraux (≈ 21,9 M sommets) est couvert par le lemme de décomposition (§5), contrôlé mais pas prouvé formellement ici ; une preuve Lean du lemme serait le prolongement naturel côté game_theory_lean. La promotion du statut de l’opération 13 dans le ledger du Chantier 1 (seconde attestation constituée) relève du coordinateur, pas de ce notebook. La ligne README de la série GameTheory est volontairement non modifiée (PR ouverte #16179 détient le fichier).
Généalogie : GameTheory-20 (témoin constructeur/vérificateur, 2×2) · GameTheory-20b (témoins d’impossibilité) · ce notebook (second substrat, verdict de frontière).