Grain1 d’ai-01 sur #12205 §6 : Robinson-Goforth (#12364, GT-20 chemin minimal) porte les points 1-3 du critere d’acceptance mais pas le point 4 (temoin d’impossibilite). Ce notebook ferme le point 4 en s’appuyant sur la structure produit des chambres : d_chambre(G,H) = d_perm(row_G,row_H) + d_perm(col_G,col_H).
Conventions reprises de GT-20 : canonique, swap_valeurs_adjacentes, swap_jeu(cote, k), 24 ordres stricts sur 4 cases, 576 chambres, 6 voisins par jeu (3 swaps x {ligne, colonne}).
0. Configuration
# === Configuration : GameTheory 24b ===from itertools import permutationsfrom collections import deque, Counterprint("GameTheory 24b : temoin d'impossibilite certifie sur R-G (point 4)")print()def canonique(t): vals =sorted(set(t))returntuple(vals.index(v) +1for v in t)def swap_valeurs_adjacentes(t, k): pk, pk1 = t.index(k), t.index(k +1) l =list(t) l[pk], l[pk1] = l[pk1], l[pk]returntuple(l)def swap_jeu(jeu, cote, k): row, col = jeuif cote =="ligne":return (swap_valeurs_adjacentes(row, k), col)return (row, swap_valeurs_adjacentes(col, k))def adj_chambre(g):return [swap_jeu(g, cote, k) for cote in ("ligne", "colonne") for k in (1, 2, 3)]def adj_perm(t):return {swap_valeurs_adjacentes(t, k) for k in (1, 2, 3)}def bfs(depart, voisins_fn): dist = {depart: 0} q = deque([depart])while q: u = q.popleft()for v in voisins_fn(u):if v notin dist: dist[v] = dist[u] +1 q.append(v)return diststricts =sorted({canonique(t) for t in permutations(range(1, 5))})chambres = [(r, c) for r in stricts for c in stricts]print(f"Permutaedre : {len(stricts)} ordres stricts, {len(adj_perm(stricts[0]))} voisins / ordre")print(f"Chambres : {len(chambres)} sommets, {len(adj_chambre(chambres[0]))} voisins / chambre")
Le graphe des chambres est un produit cartesien de deux copies du permutaedre S_4 : chaque chambre (row, col) est une paire d’ordres stricts sur 4 cases, et les generateurs ne touchent qu’un seul cote a la fois (un swap sur la ligne laisse la colonne intacte, et reciproquement).
Theoreme cle : pour tous G = (row_G, col_G) et H = (row_H, col_H) dans chambres, la distance dans le produit est exactement la somme des distances dans chaque facteur : d_chambre(G, H) = d_perm(row_G, row_H) + d_perm(col_G, col_H).
Demonstration par double inegalite :
Borne inferieure (par comptage des pas de chaque cote) : soit un chemin de G a H de longueur L dans le produit. Chaque generateur ne touche qu’un seul cote, donc les L pas se repartissent en n_row pas cote ligne et n_col pas cote colonne, avec L = n_row + n_col. En ne gardant que les pas cote ligne, on obtient un chemin de row_G a row_H dans le permutaedre, de longueur n_row : donc n_row >= d_perm(row_G, row_H), et symetriquement n_col >= d_perm(col_G, col_H). En sommant : L >= d_perm(row_G, row_H) + d_perm(col_G, col_H).
Pourquoi la projection seule ne suffit pas : projeter le chemin entier sur le facteur ligne ne preserve pas la longueur — les pas cote colonne projettent sur du surplace. On en tire d_perm(row_G, row_H) <= L, et de meme d_perm(col_G, col_H) <= L : cela borne L par le maximum des deux distances, pas par leur somme. C’est le comptage L = n_row + n_col, et lui seul, qui donne l’additivite.
Borne superieure (par concatenation) : reciproquement, un chemin optimal dans le facteur ligne (longueur d_perm(row_G, row_H)) et un chemin optimal dans le facteur colonne (longueur d_perm(col_G, col_H)) peuvent etre concatenes cote par cote pour produire un chemin de longueur d_perm(row_G, row_H) + d_perm(col_G, col_H) dans le produit (l’independance des cotes permet l’entrelacement arbitraire). Donc d_chambre(G, H) <= d_perm(row_G, row_H) + d_perm(col_G, col_H).
Conclusion : l’egalite stricte est prouvee pour toute paire (G, H). Le produit cartesien preserve exactement la distance metrique — c’est la structure produit du graphe.
# === Section 1.1 : verification exhaustive ===IDENTITE = ((1, 2, 3, 4), (1, 2, 3, 4))dist_perm = {o: bfs(o, adj_perm) for o in stricts}dist_chambre = bfs(IDENTITE, lambda g: adj_chambre(g))ecarts = []for (r, c) in chambres: d_ch = dist_chambre[(r, c)] d_calc = dist_perm[IDENTITE[0]][r] + dist_perm[IDENTITE[1]][c]if d_ch != d_calc: ecarts.append(((r, c), d_ch, d_calc))print(f"Verification exhaustive sur 576 chambres : {len(ecarts)} ecarts")print(f"Structure produit : {'EXACTE'ifnot ecarts else'NON'}")print(f"Diametre permutaedre : {max(max(d.values()) for d in dist_perm.values())}")print(f"Diametre chambres : {max(dist_chambre.values())}")assertnot ecartsprint("ASSERTION PASS : structure produit verifiee sur 576/576")
Verification exhaustive sur 576 chambres : 0 ecarts
Structure produit : EXACTE
Diametre permutaedre : 6
Diametre chambres : 12
ASSERTION PASS : structure produit verifiee sur 576/576
2. Le certificat analytique
Pour un triplet (G, H, k_max), on definit le verdict par comparaison :
IMPOSSIBLE si d_row + d_col > k_max (la distance minimale theorique depasse la borne, donc aucun chemin de longueur <= k_max n’existe) ;
POSSIBLE si d_row + d_col <= k_max (un chemin de cette longueur existe, par concatenation des chemins optimaux dans chaque facteur).
Le verdict IMPOSSIBLE porte un certificat analytique : les valeurs (d_row, d_col, k_max) qui le justifient. Le verdict POSSIBLE porte la meme garantie d’existence, mais ne fournit pas le chemin explicite — celui-ci est produit par le constructeur de GT-20 (point 1 du critere #12205 §5).
Verification de la table 24x24 : le tableau D des distances dans le permutaedre doit etre symetrique et triangulaire pour que le certificat soit coherent.
# === Section 2.1 : precalcul 24x24 ===D = {(o1, o2): dist_perm[o1][o2] for o1 in stricts for o2 in stricts}non_sym = [(o1, o2) for o1 in stricts for o2 in stricts if D[(o1,o2)] != D[(o2,o1)]]print(f"Symetrie 24x24 : {len(non_sym)} asymetries")import itertoolsviolations =sum(1for o1, o2, o3 in itertools.product(stricts, repeat=3)if D[(o1, o3)] > D[(o1, o2)] + D[(o2, o3)])print(f"Inegalite triangulaire : {violations} violations sur {24**3} triplets")assert violations ==0print("ASSERTION PASS : table 24x24 symetrique et triangulaire")
Trois cas fondateurs illustrent les regimes du certificat :
Cas A : antipode IDENTITE -> RENVERS, k_max=5 -> verdict IMPOSSIBLE (distance 12 > 5) ;
Cas B : IDENTITE vers une chambre a d_row=0, d_col=4, k_max=3 -> verdict IMPOSSIBLE (distance 4 > 3) ;
Cas C : frontiere d_row=0, d_col=1, k_max=1 -> verdict POSSIBLE (distance 1 <= 1).
L’exemple ci-dessous montre comment le verdict est obtenu a partir de la table D. Le retour est un dictionnaire {'verdict', 'd_row', 'd_col', 'd_min', 'k_max', 'preuve'} ou preuve est la chaine qui materialise l’inegalite.
CAS A (antipode, k_max=5) : IMPOSSIBLE - d_perm(row) + d_perm(col) = 6 + 6 = 12 > 5
CAS B (row identique, k_max=3) : IMPOSSIBLE - d_perm(row) + d_perm(col) = 0 + 4 = 4 > 3
CAS C (frontiere, k_max=1) : POSSIBLE - d_perm(row) + d_perm(col) = 1 + 0 = 1 <= 1
4. Verification BFS tronque
Pour chaque cas IMPOSSIBLE, on verifie par BFS tronque que H n’est jamais dans les sommets a distance <= k_max de G. Le BFS tronque collecte tous les sommats atteignables en au plus k_max pas, sans reconstruire le graphe entier — c’est un outil de verification operationnelle, distinct du certificat analytique et utile comme contre-controle.
# === Section 4.1 : BFS tronque ===def bfs_tronque(depart, voisins_fn, profondeur_max): atteints = {depart} frontiere = {depart}for d inrange(profondeur_max): nouvelle_frontiere =set()for u in frontiere:for v in voisins_fn(u):if v notin atteints: atteints.add(v) nouvelle_frontiere.add(v) frontiere = nouvelle_frontiereifnot frontiere:breakreturn atteintsatte_A = bfs_tronque(IDENTITE, lambda g: adj_chambre(g), 5)verif_A = RENVERS notin atte_Aprint(f"CAS A : sommets a <= 5 pas = {len(atte_A)}, RENVERS present ? {RENVERS in atte_A}")print(f" Temoin IMPOSSIBLE verifie : {verif_A}")atte_B = bfs_tronque(IDENTITE, lambda g: adj_chambre(g), 3)verif_B = H_B notin atte_Bprint(f"CAS B : sommets a <= 3 pas = {len(atte_B)}, H_B present ? {H_B in atte_B}")print(f" Temoin IMPOSSIBLE verifie : {verif_B}")atte_C = bfs_tronque(IDENTITE, lambda g: adj_chambre(g), 1)verif_C = H_C in atte_Cprint(f"CAS C : sommets a <= 1 pas = {len(atte_C)}, H_C present ? {H_C in atte_C}")print(f" Temoin POSSIBLE verifie : {verif_C}")assert verif_A and verif_B and verif_Cprint("ASSERTION PASS : 3 cas (2 IMPOSSIBLE, 1 POSSIBLE) verifies")
CAS A : sommets a <= 5 pas = 235, RENVERS present ? False
Temoin IMPOSSIBLE verifie : True
CAS B : sommets a <= 3 pas = 68, H_B present ? False
Temoin IMPOSSIBLE verifie : True
CAS C : sommets a <= 1 pas = 7, H_C present ? True
Temoin POSSIBLE verifie : True
ASSERTION PASS : 3 cas (2 IMPOSSIBLE, 1 POSSIBLE) verifies
5. Exemples guides – le temoin en action
Trois exemples guident pas-a-pas l’utilisation du temoin sur des structures differentes des Cas A/B/C (section 3). Chaque exemple combine verification analytique (via la table D) et verification operationnelle (via BFS tronque) pour montrer que les deux voies sont d’accord.
5.1 Exemple guide – Un autre cas IMPOSSIBLE
Demarche : on choisit une chambre H dont la structure est differente de l’antipode du Cas A — par exemple, H a la ligne antipode mais la colonne identique a G. Alors d_perm(row_G, row_H) = 6 (antipode du permutaedre) et d_perm(col_G, col_H) = 0 (meme colonne), donc d_min = 6 + 0 = 6. Pour k_max = 3, le verdict est IMPOSSIBLE puisque 6 > 3.
Verification operationnelle par BFS tronque : on enumere tous les sommets atteignables en k_max = 3 pas depuis G. Si H n’y figure pas, le verdict analytique est confirme operationnellement — c’est un contre-controle independant du certificat.
L’exemple ci-dessous execute cette verification et imprime les deux verifications (analytique + operationnelle) ; elles doivent etre d’accord.
# === Exemple guide 5.1 : un autre cas IMPOSSIBLE (row antipode, col identique) ===G_exemple = IDENTITEH_exemple = ((4, 3, 2, 1), (1, 2, 3, 4)) # row antipode, col identiquek_max_exemple =3# 6 > 3 -> IMPOSSIBLE# Verification analytique (via la table D)cert_exemple = certifier_impossibilite(G_exemple, H_exemple, k_max_exemple)print("Certificat analytique :", cert_exemple['verdict'], "-", cert_exemple['preuve'])# Verification operationnelle (BFS tronque, independante de la table)atteints_exemple = bfs_tronque(G_exemple, lambda g: adj_chambre(g), k_max_exemple)h_present = H_exemple in atteints_exempleprint(f"BFS tronque : {len(atteints_exemple)} sommets a <= {k_max_exemple} pas")print(f"H present dans le voisinage ? {h_present} (attendu : False)")print(f"Verifications d'accord : {cert_exemple['verdict'] =='IMPOSSIBLE'andnot h_present}")
Certificat analytique : IMPOSSIBLE - d_perm(row) + d_perm(col) = 6 + 0 = 6 > 3
BFS tronque : 68 sommets a <= 3 pas
H present dans le voisinage ? False (attendu : False)
Verifications d'accord : True
5.2 Exemple guide – Distance d’un antipode
Demarche : la distance entre deux sommets G et H est le plus petit k tel que H appartient aux sommets a distance <= k de G. Pour l’antipode (IDENTITE, RENVERS), le certificat analytique donne d_min = 6 + 6 = 12 — c’est le diametre du graphe produit. Le plus petit k_max qui rend POSSIBLE est donc k_max = 12 (a k_max < 12, IMPOSSIBLE est certain ; a k_max >= 12, POSSIBLE est garanti par concatenation des deux chemins optimaux).
L’exemple ci-dessous balaie les k de 0 a 12 et identifie le seuil de bascule.
# === Exemple guide 5.2 : distance de l'antipode (IDENTITE, RENVERS) ===seuil =Nonefor k inrange(0, 13): c = certifier_impossibilite(IDENTITE, RENVERS, k)if c['verdict'] =='POSSIBLE': seuil = kprint(f"Bascule IMPOSSIBLE -> POSSIBLE a k={k} (d_min = {c['d_min']})")breakprint(f"Seuil exact : {seuil}, distance de l'antipode = {c['d_min']}")
Bascule IMPOSSIBLE -> POSSIBLE a k=12 (d_min = 12)
Seuil exact : 12, distance de l'antipode = 12
5.3 Exemple guide – Paires d_row=0, d_col=6
Demarche : d_row = 0 signifie que la ligne de G est identique a la ligne de H ; d_col = 6 signifie que la colonne de G est l’antipode de la colonne de H. Ce sont donc les paires ou seul le cote colonne doit etre parcoure dans toute sa longueur.
Pour les trouver : on balaie toutes les chambres et on garde celles ou la ligne est inchangee et la colonne est antipode (par convention, l’antipode est (4, 3, 2, 1) a droite comme a gauche). Le balayage donne plusieurs solutions ; l’exemple en garde 3 et imprime leur verdict aux seuils k_max=5 (IMPOSSIBLE) et k_max=6 (frontiere, POSSIBLE).
# === Exemple guide 5.3 : trois paires d_row=0, d_col=6 ===candidates_43 = []for G in chambres:for H in chambres:if G == H:continueif D[(G[0], H[0])] ==0and D[(G[1], H[1])] ==6: candidates_43.append((G, H))iflen(candidates_43) >=3:breakiflen(candidates_43) >=3:breakfor i, (G, H) inenumerate(candidates_43, 1): c5 = certifier_impossibilite(G, H, 5) c6 = certifier_impossibilite(G, H, 6)print(f"Paire {i} : k_max=5 -> {c5['verdict']}, k_max=6 -> {c6['verdict']}")
Paire 1 : k_max=5 -> IMPOSSIBLE, k_max=6 -> POSSIBLE
Paire 2 : k_max=5 -> IMPOSSIBLE, k_max=6 -> POSSIBLE
Paire 3 : k_max=5 -> IMPOSSIBLE, k_max=6 -> POSSIBLE
6. Inventaire – combien de triplets sont IMPOSSIBLE ?
Echantillon aleatoire de 100 chambres representatives (seed=42 pour la reproductibilite), balayage des k_max ∈ {0..11}. La proportion d’IMPOSSIBLE decroît quand k_max augmente (plus la borne est large, plus il est facile de tomber dans la zone POSSIBLE ; plus elle est serree, plus l’impossibilite est facile a prouver), puis s’annule au-dela du diametre (k_max >= 12 : tout couple devient POSSIBLE).
La sortie de la cellule code plus loin trace les valeurs reelles sur le sous-echantillon :
k_max
IMPOSSIBLE / Total
%
0
57 500 / 57 500
100,0 %
1
56 900 / 57 500
99,0 %
2
55 000 / 57 500
95,7 %
3
50 800 / 57 500
88,3 %
4
43 700 / 57 500
76,0 %
5
34 100 / 57 500
59,3 %
Ces valeurs sont celles qu’imprime la cellule code qui suit immediatement (cellule de substance preservee depuis le commit 6b190bffb0 ; seule la reference de section de son commentaire d’en-tete a ete renumerotee, 5.1 -> 6.1 – ses sorties commitees n’ont pas bouge).
# === Section 6.1 : inventaire ===import randomrandom.seed(42)echantillon = random.sample(chambres, 100)resultats_par_k = {}for k_max inrange(0, 12): compteur_imp =0 compteur_tot =0for G in echantillon:for H in chambres:if G == H:continue d_min = D[(G[0], H[0])] + D[(G[1], H[1])] compteur_tot +=1if d_min > k_max: compteur_imp +=1 resultats_par_k[k_max] = (compteur_imp, compteur_tot)print("k_max | IMPOSSIBLE / Total | %")print("-"*50)for k_max in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11): imp, tot = resultats_par_k[k_max] pct =100.0* imp / totprint(f" {k_max:>2} | {imp:>6} / {tot:>6} | {pct:>5.1f}%")imp5, tot5 = resultats_par_k[5]print()print(f"A k_max=5 : {100*imp5/tot5:.1f}% des paires sont IMPOSSIBLE -- le temoin tranche souvent")
Certifie : pour k_max < 12, IMPOSSIBLE est certain des que d_min > k_max.
Non certifie : un cas POSSIBLE garantit l’existence d’un chemin, pas un chemin explicite. La construction explicite est deléguée au constructeur de GT-20 (point 1 du critere #12205 §5) qui produit le chemin par concatenation des chemins optimaux dans chaque facteur.
Au-dela de k_max = 12 (le diametre du produit), tout est POSSIBLE par definition : le chemin existe toujours en au plus 12 pas.
# === Section 7.1 : resume final ===print("RESUME -- Le point 4 du critere #12205 est TENU sur Robinson-Goforth")print()print("Verdict par cas :")print(f" CAS A : {cas_A['verdict']}")print(f" CAS B : {cas_B['verdict']}")print(f" CAS C : {cas_C['verdict']}")print()print("Verification par BFS tronque :")print(f" CAS A IMPOSSIBLE verifie : {verif_A}")print(f" CAS B IMPOSSIBLE verifie : {verif_B}")print(f" CAS C POSSIBLE verifie : {verif_C}")print()print(f"Structure produit : 576/576 chambres, 0 ecart")print(f"Table 24x24 : symetrique et triangulaire")print(f"A k_max=5 : {100*imp5/tot5:.1f}% des paires sont IMPOSSIBLE")
RESUME -- Le point 4 du critere #12205 est TENU sur Robinson-Goforth
Verdict par cas :
CAS A : IMPOSSIBLE
CAS B : IMPOSSIBLE
CAS C : POSSIBLE
Verification par BFS tronque :
CAS A IMPOSSIBLE verifie : True
CAS B IMPOSSIBLE verifie : True
CAS C POSSIBLE verifie : True
Structure produit : 576/576 chambres, 0 ecart
Table 24x24 : symetrique et triangulaire
A k_max=5 : 59.3% des paires sont IMPOSSIBLE
8. Exercices
Exercice A – Un cas IMPOSSIBLE non antipode
Trouver un couple (G, H) et un k_max tels que le verdict est IMPOSSIBLE, avec une structure differente des cas fondateurs suivants :
Cas A : antipode integral (les deux cotes a distance 6) – exhibe en cellule 8 ;
Cas B (d_row = 0, d_col = 4) : un seul cote avec une distance non antipode (4 < 6) ; aussi exhibe en cellule 8 ;
Exemple 5.1 (H_exemple = ((4, 3, 2, 1), (1, 2, 3, 4))) : un seul cote antipode (d_perm(row_G, row_H) = 6, d_perm(col_G, col_H) = 0) – l’exemple guide de la section 5.
L’enonce de l’exercice exclut donc l’antipode integral (Cas A) et les mono-cotes antipodes (exemple 5.1) et les mono-cotes non antipodes (Cas B). Reste ce qui n’appartient a aucune de ces trois familles : par exemple, les deux cotes a des distances intermediaires (3 et 4, par exemple) pour un k_max = 5. Verifier par BFS tronque que le verdict certifie est bien IMPOSSIBLE.
# Exercice A : cas IMPOSSIBLE non antipode# A l'etudiant : choisir G, H, k_max de sorte que d_row + d_col > k_max# avec une structure differente des Cas A/B/5.1.G_A =None# TODO etudiantH_A =None# TODO etudiantk_max_A =None# TODO etudiantresultat_A =None# TODO etudiant# Verification par l'etudiant :# 1. cert = certifier_impossibilite(G_A, H_A, k_max_A)# 2. atteints = bfs_tronque(G_A, lambda g: adj_chambre(g), k_max_A)# 3. assert cert['verdict'] == 'IMPOSSIBLE' and H_A not in atteints
Exercice B – Structure produit pour un G arbitraire
Verifier que la structure produit reste valide pour un G de depart qui n’est pasIDENTITE — par exemple G = ((2, 1, 4, 3), (3, 4, 1, 2)). La structure produit est-elle toujours d_chambre(G, H) = d_perm(row_G, row_H) + d_perm(col_G, col_H), ou faut-il la reformuler ?
# Exercice B : verifier la structure produit pour un G != IDENTITEG_B = ((2, 1, 4, 3), (3, 4, 1, 2)) # un G arbitraire (non IDENTITE)# A l'etudiant :# 1. Calculer dist_chambre_G = bfs(G_B, lambda g: adj_chambre(g))# 2. Pour chaque H in chambres, comparer dist_chambre_G[H] a# D[(G_B[0], H[0])] + D[(G_B[1], H[1])]# 3. Conclure : la structure produit tient-elle ? Pourquoi ?ecarts_B =None# TODO etudiantresultat_B =None# TODO etudiant
Exercice C – Densite d’IMPOSSIBLE a k_max=7 par echantillonnage stratifie
La section 6 a montre une densite a k_max=5 sur 100 chambres aleatoires. Estimer la densite a k_max=7 en utilisant un echantillon stratifie : le scaffold ci-dessous partitionne le permutaedre en 7 strates selon la distance a IDENTITE (0 a 6) et tire 4 chambres dans chaque strate. Completer le comptage de la proportion d’IMPOSSIBLE, puis comparer au chiffre donne par la section 6 (qui utilise un echantillon aleatoire non stratifie).
# Exercice C : densite IMPOSSIBLE a k_max=7 par echantillonnage stratifieimport randomrandom.seed(2025) # graine differente de la section 6 (seed=42)# Stratification par distance a IDENTITE dans le permutaedredef dist_id(t):return D[(IDENTITE[0], t)]stricts_par_dist = {d: [t for t in stricts if dist_id(t) == d] for d inrange(7)}echantillon_stratifie = []for d inrange(7): echantillon_stratifie.extend(random.sample(stricts_par_dist[d],min(4, len(stricts_par_dist[d]))))# A l'etudiant :# 1. Pour chaque G dans echantillon_stratifie, pour chaque H dans chambres,# compter les IMPOSSIBLE a k_max=7 (en evitant G == H)# 2. Comparer au chiffre aleatoire de la section 6resultat_C =None# TODO etudiant
Conclusion – le point 4 sur Robinson-Goforth est tenu
Acceptance #12205 §5 :
Substrat dont le verificateur existe sur main : GT-20 porte les points 1-3. OUI.
Generateur != verificateur : certifier_impossibilite (O(1)) != BFS exhaustif (O(V + E) sur la boule visitée, ici O(576 + 3 456) par palier). OUI.
Cas sans solution = temoin d’impossibilite, pas silence : section 4 verifie par BFS tronque. Section 6 : plus de la moitie des paires a k_max=5 sont IMPOSSIBLE. OUI.
Structure du notebook : - Sections 1-2 : preuve analytique de la structure produit (borne inf + borne sup) ; - Section 3 : 3 cas fondateurs A/B/C ; - Section 4 : verification operationnelle par BFS tronque ; - Section 5 : 3 exemples guides integres a la narration (5.1, 5.2, 5.3) ; - Sections 6-7 : inventaire, frontiere et bornes ; - Section 8 : 3 exercices non corriges (A, B, C) avec stubs TODO etudiant.