# -*- coding: utf-8 -*- # Verificateur de la note "Partial results on polynomial removal for the ordered 2x2 corner pattern". # Python pur (ni numpy ni scipy). Parametres fixes ci-dessous. Duree : environ 4 minutes au plus. import random, time, math, sys DUREE_PAR_TEST = 40.0 # secondes par test (5 tests) GRAINE = 20261118 def pr(*a): print(*a, flush=True) # ---------- outils ---------- def sans_coin(M): """vrai si la matrice ne contient pas le coin (lignes i k: k = d return k def sans_coin_alea(rng, n, w, cols, p): M = [[0] * w for _ in range(n)] for y in range(n): cur = [] for c in reversed(cols): if rng.random() < p: ok = True for x in range(y): if M[x][c]: for d in cur: if not M[x][d]: ok = False; break if not ok: break if ok: M[y][c] = 1; cur.append(c) return M # ---------- auto-test ---------- def autotest(): assert 7 * 6 == 42 and 2 ** 10 == 1024 and 17 % 5 == 2 assert not sans_coin([[1, 0], [1, 1]]) and sans_coin([[1, 1], [1, 0]]) and sans_coin([[0, 1], [1, 1]]) assert dist_paire([1, 0], [1, 1]) == 1 and dist_paire([1, 1, 0, 0], [1, 1, 1, 1]) == 2 and dist_paire([1, 1], [1, 1]) == 0 pr("auto-test : OK") # ---------- test 1 : formule de coupe et queue (lemme 3) ---------- def test_coupe(rng): t0 = time.time(); n = 0; bad = 0 while time.time() - t0 < DUREE_PAR_TEST: w = rng.randint(1, 14) x = [1 if rng.random() < 0.5 else 0 for _ in range(w)]; y = [1 if rng.random() < 0.6 else 0 for _ in range(w)] d = dist_paire(x, y) best = min(sum(1 for c in range(cut) if x[c] and y[c]) + sum(1 for c in range(cut, w) if y[c] and not x[c]) for cut in range(w + 1)) com = set(c for c in range(w) if x[c] and y[c]); ones = [c for c in range(w) if y[c]] tail = set(ones[len(ones) - len(com):]) if com else set() n += 1 if best != d or len(com.symmetric_difference(tail)) > 2 * d: bad += 1 if n % 200000 == 0: pr(" ...", n, "paires") return n, bad # ---------- test 2 : collage de m intervalles (theoreme 4) ---------- def colle_m(M, parts, s): n = len(M); m = len(parts) def tr(lst): return lst[:max(0, len(lst) - s)] T = [[frozenset(tr([c for c in parts[i] if M[y][c]])) for i in range(m)] for y in range(n)] N = [[0] * len(M[0]) for _ in range(n)]; cpre = [[0] * m for _ in range(n)] anc = [set() for _ in range(n)] for j in range(m): if j >= 1: i = j - 1 for y in range(n): for x in range(y): if T[x][i] & T[y][i]: anc[y].add(x) change = True while change: change = False for y in range(n): new = set(anc[y]) for x in anc[y]: new |= anc[x] if len(new) != len(anc[y]): anc[y] = new; change = True for y in range(n): Q = [c for c in parts[j] if M[y][c] and all(M[z][c] for z in anc[y])] cpre[y][j] = sum(M[y][c] for c in parts[j]) - len(Q) for c in tr(Q): N[y][c] = 1 ctot = [sum(1 for a, b in zip(M[y], N[y]) if a != b) for y in range(n)] return N, cpre, ctot def test_collage(rng): t0 = time.time(); n_ = 0; bad = 0; applic = 0; viol = 0 while time.time() - t0 < DUREE_PAR_TEST: n = rng.randint(3, 10); m = rng.choice([2, 2, 3, 4]); widths = [rng.randint(1, 7) for _ in range(m)]; w = sum(widths) parts = []; a = 0 for wd in widths: parts.append(list(range(a, a + wd))); a += wd M = [[0] * w for _ in range(n)] for P in parts: Mj = sans_coin_alea(rng, n, w, P, rng.choice([0.4, 0.7, 0.9])) for x in range(n): for c in P: M[x][c] = Mj[x][c] K = Kmax(M); s = rng.randint(0, max(widths)) N, cpre, ctot = colle_m(M, parts, s); n_ += 1 if not sans_coin(N): bad += 1 if K >= 1 and s >= 2 * K and s * s >= 4 * K * w: applic += 1 if max(max(r) for r in cpre) >= 2 * s or max(ctot) >= 3 * m * s: viol += 1 if n_ % 5000 == 0: pr(" ...", n_, "matrices") return n_, bad, applic, viol # ---------- test 3 : familles (propositions 7, 8, 14) : hypotheses ---------- def chaine(n0, h): W = (n0 + 1) * h + (n0 - 1); M = [[0] * W for _ in range(n0)] for i in range(1, n0 + 1): for b in (i, i - 1): s0 = (n0 - b) * h for c in range(s0, s0 + h): M[i - 1][c] = 1 for j in range(2, i + 1): M[i - 1][(n0 + 1) * h + (n0 - j)] = 1 return M, list(range((n0 + 1) * h)), list(range((n0 + 1) * h, W)) def fenetres(n, L): WA = n - 1 + L; T = (n - 1) // (L - 1); W = WA + T; M = [[0] * W for _ in range(n)] for i in range(n): for c in range(n - 1 - i, n - 1 - i + L): M[i][c] = 1 for t in range(1, i // (L - 1) + 1): M[i][WA + (T - t)] = 1 return M, list(range(WA)), list(range(WA, W)) def restr(M, cols): return [[r[c] for c in cols] for r in M] def verrous(m2, k, r): nb = m2 * k; c = 2 * nb; w = c + 2 + k; B = []; bas = [] for i in range(m2): B.append([1 if (i * k <= col < (i + 1) * k) or col == c else 0 for col in range(w)]) for j in range(m2): B.append([1 if (nb + j * k <= col < nb + (j + 1) * k) or col >= c else 0 for col in range(w)]) for i in range(m2): for _ in range(r): bas.append([1 if (i * k <= col < (i + 1) * k) or col == c else 0 for col in range(w)]) for j in range(m2): for _ in range(r): bas.append([1 if (nb + j * k <= col < nb + (j + 1) * k) or col == c else 0 for col in range(w)]) return B, bas def melees(B): w = len(B[0]); T10 = set(); T11 = set() for r in B: for c in range(w): if r[c]: for d in range(c + 1, w): if r[d]: T11.add((c, d)) else: T10.add((c, d)) return len(T10 & T11) def test_familles(): ok = True for n0, h in [(3, 2), (5, 4), (7, 6), (9, 8), (12, 10)]: M, A, B = chaine(n0, h) good = sans_coin(restr(M, A)) and sans_coin(restr(M, B)) and Kmax(M) == 1 pr(" chaine n0 =", n0, "h =", h, ": parties sans coin et distance des paires 1 :", good); ok = ok and good for n, L in [(60, 6), (120, 16), (150, 30)]: M, A, B = fenetres(n, L) good = sans_coin(restr(M, A)) and sans_coin(restr(M, B)) and Kmax(M) == 1 pr(" fenetres n =", n, "L =", L, ": parties sans coin et distance des paires 1 :", good); ok = ok and good for m2, k, r in [(2, 2, 2), (3, 3, 3), (3, 4, 4), (2, 6, 6)]: B, bas = verrous(m2, k, r); M = B + bas; nB = len(B); good = (melees(B) == k + 1) and (melees(bas) == 0) for i in range(len(M)): for j in range(i + 1, len(M)): if j >= nB and not sans_coin([M[i], M[j]]): good = False pr(" verrous m =", 2 * m2, "k =", k, "r =", r, ": k+1 couples meles dans B, aucun dessous, copies toutes dans B :", good); ok = ok and good return ok # ---------- test 4 : critere des seuils (lemme 9) ---------- INF = 10 ** 9 def test_seuils(rng): t0 = time.time(); n_ = 0; bad = 0; libres = 0 while time.time() - t0 < DUREE_PAR_TEST: m = rng.choice([2, 3, 3, 4]); w = rng.randint(m, 11); n = rng.randint(2, 6) cls = [rng.randrange(m) for _ in range(w)]; S = [[c for c in range(w) if cls[c] == j] for j in range(m)] st = [[(rng.choice(S[j] + [INF]) if S[j] else INF) for j in range(m)] for _ in range(n)] if rng.random() < 0.5: base = st[0]; st = [[(max(base[j], st[x][j]) if rng.random() < 0.8 else st[x][j]) for j in range(m)] for x in range(n)] M = [[1 if c >= st[x][cls[c]] else 0 for c in range(w)] for x in range(n)] theta = {}; ok = True for y in range(n): for i in range(m): for j in range(i + 1, m): if max(st[y][i], st[y][j]) <= theta.get((i, j), -1): ok = False for i in range(m): for j in range(m): if i != j and st[y][i] < st[y][j]: g = [c for c in S[j] if st[y][i] < c < st[y][j]] if g: key = (min(i, j), max(i, j)); theta[key] = max(theta.get(key, -1), g[-1]) a = sans_coin(M); n_ += 1; libres += 1 if a else 0 if a != ok: bad += 1 if n_ % 200000 == 0: pr(" ...", n_, "matrices") return n_, libres, bad # ---------- test 5 : deux classes, au plus 4K par ligne (theoreme 10) ---------- def suiv(Sj, v): for c in Sj: if c > v: return c return INF def compte(Sj, a, b): return sum(1 for c in Sj if a <= c < b) def deux_temps(n, S, st, K): N = [] for x in range(n): p = st[x][:] if p[0] != p[1]: i, j = (0, 1) if p[0] < p[1] else (1, 0) G = [c for c in S[j] if p[i] < c < p[j]] if len(G) <= K: if G: p[j] = G[0] else: p[j] = G[-K]; th = G[-K - 1] if compte(S[i], p[i], th) <= K: p[i] = suiv(S[i], th) N.append(p) fin = []; theta = None for y in range(n): p = N[y][:] if theta is not None and max(p) <= theta[0]: lev, i, j = theta if st[y][j] <= lev: p[i] = suiv(S[i], lev) else: p[j] = suiv(S[j], lev) fin.append(p) if p[0] != p[1]: i, j = (0, 1) if p[0] < p[1] else (1, 0) G = [c for c in S[j] if p[i] < c < p[j]] if G and (theta is None or G[-1] > theta[0]): theta = (G[-1], i, j) return fin def test_deux_classes(rng): t0 = time.time(); n_ = 0; bad = 0; pire = 0.0 while time.time() - t0 < DUREE_PAR_TEST: w = rng.choice([6, 8, 10, 14, 18]); n = rng.randint(3, 14) cls = [rng.randrange(2) for _ in range(w)]; S = [[c for c in range(w) if cls[c] == j] for j in range(2)] if not S[0] or not S[1]: continue base = [rng.choice(S[j] + [INF]) for j in range(2)] st = [] for x in range(n): if rng.random() < 0.5: st.append([rng.choice(S[j] + [INF]) for j in range(2)]) else: r = [] for j in range(2): lst = S[j] + [INF]; k0 = lst.index(base[j]); k1 = max(0, min(len(lst) - 1, k0 + rng.randint(-2, 2))); r.append(lst[k1]) st.append(r) M = [[1 if c >= st[x][cls[c]] else 0 for c in range(w)] for x in range(n)] K = Kmax(M) if K == 0: continue fin = deux_temps(n, S, st, K) N = [[1 if c >= fin[x][cls[c]] else 0 for c in range(w)] for x in range(n)] cout = max(sum(1 for a, b in zip(M[x], N[x]) if a != b) for x in range(n)); n_ += 1 if (not sans_coin(N)) or cout > 4 * K: bad += 1 if cout / float(K) > pire: pire = cout / float(K) if n_ % 5000 == 0: pr(" ...", n_, "matrices") return n_, bad, pire def main(): pr("Verificateur - coin 2x2 - note du 18 novembre 2026"); autotest(); rng = random.Random(GRAINE); recap = [] pr("Test 1 : formule de coupe et ecart a la queue") n, bad = test_coupe(rng); recap.append(("coupe et queue", n, bad)); pr(" paires :", n, "| echecs :", bad) pr("Test 2 : collage de m intervalles sans coin") n, bad, ap, vi = test_collage(rng); recap.append(("collage (sortie sans coin)", n, bad)); recap.append(("collage (bornes de cout)", ap, vi)); pr(" matrices :", n, "| sorties avec coin :", bad, "| cas ou la borne s'applique :", ap, "| violations :", vi) pr("Test 3 : hypotheses des trois familles") ok = test_familles(); recap.append(("familles", 12, 0 if ok else 1)) pr("Test 4 : critere des seuils pour les matrices en escaliers") n, lib, bad = test_seuils(rng); recap.append(("critere des seuils", n, bad)); pr(" matrices :", n, "| sans coin :", lib, "| desaccords :", bad) pr("Test 5 : deux classes, au plus 4K changements par ligne") n, bad, pire = test_deux_classes(rng); recap.append(("deux classes", n, bad)); pr(" matrices :", n, "| echecs :", bad, "| plus grand cout d'une ligne / K :", round(pire, 2)) pr(""); pr("=========== RECAPITULATIF ===========") tout = True for nom, n, bad in recap: pr("%-28s cas : %8d echecs : %d" % (nom, n, bad)); tout = tout and (bad == 0) pr("RESULTAT GLOBAL :", "TOUT EST CONFORME" if tout else "AU MOINS UN ECHEC") main() input("Appuyez sur Entree pour fermer...")