""" Try to construct a 6-day schedule using the 8-triangles structure. 24 vertices partitioned into 8 triangles of 3. Each day: pair triangles into 4 pairs, forming 4 boats of 6. The n=3 graph: internal edges of triangles (degree 2) + cross edges (degree 1). """ import itertools, math, json N = 24 TOTAL = 276 def norm(p,q): return (min(p,q), max(p,q)) def count_pairs(sched): pairs = set() for day in sched: for b in day: pairs.update(norm(p,q) for p,q in itertools.combinations(b, 2)) return len(pairs) def missing_pairs(sched): pairs = set() for day in sched: for b in day: pairs.update(norm(p,q) for p,q in itertools.combinations(b, 2)) return set(norm(i,j) for i in range(N) for j in range(i+1,N)) - pairs # 8 triangles of 3 vertices each triangles = [ [0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11], [12, 13, 14], [15, 16, 17], [18, 19, 20], [21, 22, 23], ] # Label each vertex with its triangle and position # T[i] = triangle i # T[i][j] = j-th vertex of triangle i # We need 6 pairings of triangles. # Each pairing is a perfect matching of K_8 (4 disjoint pairs). # Different days use different pairings. # Let me generate all perfect matchings of K_8 and pick 6 of them. # Number of perfect matchings of K_8: 8!/(2^4 * 4!) = 105. def all_perfect_matchings(n=8): """Generate all perfect matchings of K_n (n even).""" if n == 0: yield [] return first = 0 for second in range(1, n): rest = [i for i in range(1, n) if i != second] for matching in all_perfect_matchings(n-2): # Remap indices remap = {} for idx, val in enumerate(rest): remap[val] = idx + 1 remapped = [] for pair in matching: remapped.append(tuple(sorted([remap[pair[0]], remap[pair[1]]]))) yield [(first, second)] + remapped matchings = list(all_perfect_matchings(8)) print(f"Total perfect matchings of K_8: {len(matchings)}") # We need 6 matchings (one per day) such that all pairs of triangles # are covered some number of times. # # n=3 graph edges (3-regular on 24 vertices): # Each triangle has 3 internal edges. 8 × 3 = 24 internal edges. # Plus 12 cross edges (one per vertex, connecting to a vertex in another triangle). # # For internal edges: they appear in the boat whenever their triangle is paired # with any other triangle. Since each triangle is paired on all 6 days, # each internal edge appears on all 6 days → n=6. That's too many! # We want n=3 for these edges. # So the simple "same triangle = always together" approach gives n=6, not n=3. # I need the internal edges to only appear in some of the days. # This means: on some days, the triangle members must be SPLIT across different boats. # This defeats the purpose of the triangle structure. # The n=3 graph can't simply be 8 triangles with cross connections, # because the internal edges would have too high multiplicity. # Let me reconsider: the n=3 graph is a 3-regular graph on 24 vertices. # The internal edges of triangles would give degree 2 (within triangle). # Cross edges give degree 1. Total degree 3. ✓ # But internal edges appear whenever the triangle is together (every day), # giving n=6, not n=3. # Fix: Don't keep triangles together every day. On some days, split them. # This reduces the internal edge multiplicities. # So the construction is: pick 8 triples as "base groups" for the 3-regular graph. # Internal edges: all 3 pairs within each triple (3 per triple × 8 = 24 edges). # Cross edges: 1 per vertex, connecting to a vertex in a different triple (12 edges). # Total: 36 edges (the 3-regular graph). # These 36 edges must appear on exactly 3 days each. # Other 276 - 36 = 240 edges must appear on exactly 1 day each. # Wait, I also need 12 edges with n=2 (the 2-meeting graph). # Hmm, let me recalculate. # # For 6 days: sum (n-1) = 84. # If 36 n=3 pairs: contribution to sum (n-1) = 36×2 = 72. # Need 12 more from n=2 pairs: 12×1 = 12. Total: 72 + 12 = 84. ✓ # # O_sum = 36×3 + 12×1 = 108 + 12 = 120. ✓ # # So: 36 pairs with n=3, 12 pairs with n=2, 228 pairs with n=1. # Total distinct: 36 + 12 + 228 = 276. ✓ # Total occurrences: 36×3 + 12×2 + 228×1 = 108 + 24 + 228 = 360. ✓ # Let me implement the construction properly. # Strategy: # 1. Define 8 groups of 3 (triples that will be n=3 connected) # 2. On each day, pair triples in different ways # 3. The triples might be split across boats on some days to reduce edge multiplicity # Let me try: on each day, pair the 8 triples into 4 pairs (each boat gets 2 triples). # The internal edges appear only when the triple is together in the same boat. # If a triple is split, its internal edges don't appear. # Each triple has 3 vertices. When paired with another triple in a boat: # The boat has 6 vertices (the 2 triples combined). # This gives all pairs within and between the triples. # For each triple, its internal edges appear in the day if the triple is # kept together (not split). # If I keep triples together every day: internal edges appear 6 times. Not good. # If I split triples on some days: internal edges appear fewer times. # To get n=3 for internal edges: each triple should be kept together on exactly 3 days # and split on the other 3 days. # When a triple is split: its 3 vertices go to different boats (1 per boat). # Since there are 4 boats, I put 1 vertex in each of 3 boats, and the 4th boat # gets no one from this triple. # This is getting complicated. Let me just try running the construction # and seeing what coverage we get. # Simple version: different triangle pairings on different days. # All 8 triangles are kept intact every day. # Different perfect matchings on different days. # This gives: internal edges n=6 (too high), cross edges vary. # Let me check: with 6 different perfect matchings of 8 vertices (triangles), # what does the coverage look like? def schedule_from_matchings(matchings): """Given 6 perfect matchings of 8 vertices, build a schedule.""" sched = [] for matching in matchings: boats = [] for (t1, t2) in matching: boat = sorted(triangles[t1] + triangles[t2]) boats.append(tuple(boat)) sched.append(boats) return sched # Pick 6 good matchings # Let me try the 6 "parallel classes" of the octahedron # or just try many random sets import random as rnd # Try all combinations of 6 matchings? 105 choose 6 is too many. # Let me try a greedy approach. def greedy_select_matchings(): selected = [] covered_edges = set() # We need that each of the C(24,2) = 276 pairs is covered at least once. # Pairs within the same triple (triplet pairs): each triple has 3 pairs. # These will be covered every day (since triple together every day). # Cross-triplet pairs: 9 pairs for each pair of triples. # There are C(8,2) = 28 pairs of triples. # Each matching covers 4 pairs of triples (one per boat). # So 4 × 9 = 36 cross-triplet pairs per day. # Over 6 days, if all 28 pairs of triples are covered at least once: # 28 × 9 = 252 cross-triplet pairs. # Plus 8 × 3 = 24 within-triplet pairs. # Total: 276 ✓ # So I need to cover all 28 pairs of triples with 6 matchings. # Each matching covers 4 pairs of triples. # 6 × 4 = 24 edge-covers of the K_8 graph (where vertices are triples). # Need to cover all 28 edges of K_8. # 24 < 28, so some edges are NOT covered. ✗ # This means with 6 matchings of K_8, we can only cover 24 of the 28 # pairs of triples. The remaining 4 pairs are never together. # That's 4 × 9 = 36 cross-triplet pairs lost. # But the within-triplet pairs (24) are all covered on all 6 days. # So distinct pairs = 24 + 24×9 = 24 + 216 = 240. # Same as the affine plane construction! Missing 36 pairs. # To cover all 28 pairs of triples, I need at least 7 matchings. # But 7 matchings would give 7 × 4 = 28, covering all 28 edges exactly once. # 7 matchings = 7 days. But then within-triplet pairs appear 7 times (n=7). # Excess: 24 × 6 + (all cross edges × 0) = 144. Total occurrences = 420. # Distinct pairs = 24 + 28 × 9 = 24 + 252 = 276. ✓ # So 7 days works with the triangle pairing approach! # But earlier I showed 6 days is possible in theory. # The 8-triangle structure might require 7 days. # Let me try a different structure. return [] print("\nTriangle analysis:") print(f" Within-triangle pairs (n=6 if always together): 8 × 3 = 24") print(f" Cross-triangle pairs per matching: 4 × 9 = 36") print(f" Total pairs per matching: 24 + 36 = 60") print(f" 6 matchings: 6 × 4 = 24 edge-covers of K_8") print(f" Need 28, missing 4 pairs of triangles") print(f" Missing pairs: 4 × 9 = 36") # So the 8-triangle approach is equivalent to the affine plane approach # in terms of coverage (240/276). It gives the same structure. # For 7 days: 7 matchings cover all 28 edges of K_8 exactly once. # Each within-triangle pair appears 7 times. # Each cross-triangle pair appears exactly once. # Total distinct: 24 + 28×9 = 24 + 252 = 276. ✓ # So 7 DAYS is achievable with this simple structure! # The schedule is just the 7 1-factorizations of K_8. # K_8 can be decomposed into 7 perfect matchings (1-factorization of K_8). print("\n7-DAY SOLUTION EXISTS!") print("K_8 has a 1-factorization into 7 perfect matchings.") print("Each matching pairs groups of 3 into boats of 6.") print("This gives a valid 7-day schedule.") # Let me construct the 7-day schedule explicitly. # A 1-factorization of K_8 with vertices 0-7: # Factor 1: (0,1), (2,3), (4,5), (6,7) # Factor 2: (0,2), (1,3), (4,6), (5,7) # Factor 3: (0,3), (1,2), (4,7), (5,6) # Factor 4: (0,4), (1,5), (2,6), (3,7) # Factor 5: (0,5), (1,4), (2,7), (3,6) # Factor 6: (0,6), (1,7), (2,4), (3,5) # Factor 7: (0,7), (1,6), (2,5), (3,4) # Each factor gives 4 pairs of triangles, forming 4 boats of 6. # This creates a 7-day schedule covering ALL 276 pairs! one_factorization = [ [(0,1), (2,3), (4,5), (6,7)], [(0,2), (1,3), (4,6), (5,7)], [(0,3), (1,2), (4,7), (5,6)], [(0,4), (1,5), (2,6), (3,7)], [(0,5), (1,4), (2,7), (3,6)], [(0,6), (1,7), (2,4), (3,5)], [(0,7), (1,6), (2,5), (3,4)], ] sched7 = schedule_from_matchings(one_factorization) cov7 = count_pairs(sched7) print(f"\n7-day schedule coverage: {cov7}/{TOTAL}") if cov7 == TOTAL: print("SUCCESS! All pairs covered!") for i, day in enumerate(sched7): print(f" Day {i+1}: {day}") print(f"\nJSON:\n{json.dumps(sched7)}") else: print(f"Missing: {missing_pairs(sched7)}")