# How Many Days Does the Regatta Need?

**The problem.** 24 rowers, 4 boats, each boat holds exactly 6 people.
Each day the coxswain assigns everyone to boats (a partition of 24 into
4 groups of 6). The goal: ensure that **every possible pair** of rowers
shares a boat on at least one day. How many days must the meet last?

With $\binom{24}{2}=276$ distinct pairs and 4 boats × $\binom{6}{2}=15$
pairs per day, each day covers 60 pairs. A naïve bound:
$\lceil 276/60\rceil = 5$ days. But can we actually do it in 5?

This is a combinatorial design problem — a *resolvable covering design*
to be precise. Let's see what happened when I tried to solve it.

---

## Attempt 1: Just search for it

The search space is enormous. Each day is one way to split 24 labelled
people into 4 unlabelled groups of 6. The number is:

$$\frac{24!}{(6!)^4 \cdot 4!} \approx 4.5 \times 10^{11}$$

and we need 5 or 6 of these simultaneously. Brute force is right out.

I wrote a **local search** / simulated annealing script. Start with
random partitions, try swapping two people between boats, keep changes
that improve coverage. It quickly reached about 256/276 and then
stalled. No amount of tuning got past 256 with 5 days.

```python
# Pseudocode for the simple local search
def local_search(days, iterations):
    schedule = [random_partition() for _ in range(days)]
    for _ in range(iterations):
        d = random_day()
        swap_two_people(schedule[d])
        if coverage(schedule) improved: keep it
        else: revert
```

I tried 6 days instead of 5. The search climbed to 271, then 274.
Stuck again. Here's the best I ever got with 6 days — just **2 pairs**
short:

```
Coverage: 274/276
Missing: [(1, 6), (8, 23)]
```

I couldn't squeeze past it. Something deeper was blocking 5 days.

---

## Attempt 2: Algebraic constructions

Maybe I could construct the schedule by hand using algebra. Label
rowers as $(x, y)$ where $x \in \mathbb{Z}_6$ and $y \in \mathbb{Z}_4$.
Define days by functions $f(x,y) = (ax + by) \bmod 4$.

Most of these functions give 4 balanced groups of 6 (each residue
appears exactly 6 times). With 6 such linear functions I covered
only 184 pairs — worse than random search.

I tried quadratic functions, cosets, the affine plane of order 5
(with one point removed), and the $ \mathbb{Z}_6 \times \mathbb{Z}_4$
grid in various configurations. Nothing got close to 276.

Here's the affine plane approach: the affine plane over GF(5) has
25 points, 6 parallel classes of 5 lines each (each line size 5).
Remove one point — now 24 points, each class has one line of size 4
and four lines of size 5. Add one person from the size-4 line to each
size-5 line to make boats of 6. This gave 240/276 — the same 36 pairs
(the "at-risk" pairs from the size-4 lines) were always missing.

```python
# Affine plane adaptation: 240/276
for each parallel class K:
    size4_line, size5_lines = K  # 1 line of 4, 4 lines of 5
    for i in range(4):
        boat_i = size5_lines[i] + [size4_line[i]]
```

**The pattern.** Every approach hit a ceiling. The 36 at-risk pairs
were always the missing ones. This suggested a fundamental obstruction.

---

## The key insight: minimum partition overlap

Two different days give two partitions $P$ and $Q$ of the 24 rowers
into 4 boats of 6. How many pairs are together in *both* partitions?

For each boat $G_i$ in $P$, its 6 people are spread across the 4 boats
of $Q$. To minimize the number of pairs that repeat, we spread them as
evenly as possible: $(2,2,1,1)$ gives $\binom{2}{2}+\binom{2}{2}=2$
overlapping pairs from $G_i$.

With 4 boats in $P$, that's **at least 8 overlapping pairs** between
any two days. And this is tight — here's an explicit pair of partitions
with exactly 8 overlaps:

| $G_i$ \ $H_j$ | $H_1$ | $H_2$ | $H_3$ | $H_4$ |
|:---:|:---:|:---:|:---:|:---:|
| $G_1$ | 2 | 2 | 1 | 1 |
| $G_2$ | 2 | 2 | 1 | 1 |
| $G_3$ | 1 | 1 | 2 | 2 |
| $G_4$ | 1 | 1 | 2 | 2 |

Total overlap: $4 \times 2 = 8$.

---

## Proving 5 days is impossible

With 5 days, there are $\binom{5}{2} = 10$ pairs of days. Each pair
contributes at least 8 overlapping pairs, so the **sum of all pairwise
overlaps** is at least $10 \times 8 = 80$.

Let $n_{pq}$ be the number of days that rowers $p$ and $q$ are together.
The total pair-occurrences (counting multiplicities) is:

$$\sum_{p<q} n_{pq} = 5 \times 60 = 300$$

We need 276 distinct pairs, so the "excess" (repeated meetings) is:

$$\sum_{p<q} (n_{pq} - 1) = 300 - 276 = 24$$

The sum of pairwise overlaps equals $\sum_{p<q} \binom{n_{pq}}{2}$.

Here's the crunch: given that $\sum (n_{pq}-1) = 24$, what's the
maximum possible $\sum \binom{n_{pq}}{2}$? Each pair with $n_{pq}=t$
contributes $t-1$ to the excess and $\binom{t}{2}$ to the overlaps.
The best ratio comes from concentrating excess into pairs together
every day:

| $t$ | excess $(t-1)$ | overlaps $\binom{t}{2}$ | efficiency |
|:---:|:---:|:---:|:---:|
| 2 | 1 | 1 | 1.0 |
| 3 | 2 | 3 | 1.5 |
| 4 | 3 | 6 | 2.0 |
| 5 | 4 | 10 | 2.5 |

Maximum: put all 24 excess into $n=5$ pairs (together all 5 days):
$24/4 = 6$ such pairs, giving $\sum\binom{n_{pq}}{2}=6\times 10 = 60$.

So $\sum\binom{n_{pq}}{2} \le 60$ for any 5-day schedule.
But the partition overlap bound forces $\sum\binom{n_{pq}}{2} \ge 80$.

**$60 < 80$ → impossible.** Five days just doesn't give enough
pair-slots to overcome the forced overlaps.

---

## Can 6 days work?

For 6 days the numbers are:

- Total pair-occurrences: $6 \times 60 = 360$
- Excess: $360 - 276 = 84$
- Pairs of days: $\binom{6}{2} = 15$
- Minimum overlap sum: $15 \times 8 = 120$

Maximum $\sum\binom{n_{pq}}{2}$ given excess 84:
concentrate into $n=6$ pairs (together every day). $84/5 = 16.8$,
so about $16 \times 15 + \dots \approx 250$. That's well above 120.

So the counting says 6 days is **possible** in theory. Each rower
would need to meet 3 people on 3 different days ($n=3$), 1 person
on 2 days ($n=2$), and everyone else once.

I searched hard — local search, genetic algorithms, multiple restarts,
the best 6-day schedule I found still missed 2 pairs. Maybe 6 is
possible but incredibly hard to find. Maybe there's another obstruction
I'm missing. I'll note this as an open question.

But I *did* find a clean 7-day construction.

---

## Breakthrough: 8 triples

The idea came from thinking about the $K_8$ complete graph. What if I
group the 24 rowers into **8 triples of 3**?

$$
\begin{aligned}
T_0 &= \{0,1,2\}, &
T_1 &= \{3,4,5\}, \\
T_2 &= \{6,7,8\}, &
T_3 &= \{9,10,11\}, \\
T_4 &= \{12,13,14\}, &
T_5 &= \{15,16,17\}, \\
T_6 &= \{18,19,20\}, &
T_7 &= \{21,22,23\}.
\end{aligned}
$$

Each day, pair the 8 triples into 4 pairs. A pair $(T_i, T_j)$ fills
one boat with $3+3=6$ people. Every cross-triple pair of rowers is
covered exactly when their triples are paired.

So I need to pair up triples so that **every pair of triples** meets
at least once. This is exactly a **1-factorization** of $K_8$ — a
decomposition of the complete graph on 8 vertices into 7 perfect
matchings. $K_8$ has exactly $8-1=7$ of these.

That's it. Exactly 7 days, and it's optimal because:

- **Within each triple**: the 3 pairs are together every day.
  $8 \times 3 = 24$ pairs covered.
- **Across triples**: each pair of triples is paired exactly once,
  giving $3\times 3 = 9$ cross pairs. $\binom{8}{2} = 28$ pairs
  of triples → $28 \times 9 = 252$ pairs covered.

Total: $24 + 252 = 276$. All pairs covered. ✓

---

## The 7-Day Schedule

The 1-factorization of $K_8$ (vertices $0,\dots,7$ → triples
$T_0,\dots,T_7$) uses the round-robin tournament schedule:

| Day | Pairings |
|:---:|:---|
| 1 | $(0,7),\,(1,6),\,(2,5),\,(3,4)$ |
| 2 | $(1,7),\,(2,0),\,(3,6),\,(4,5)$ |
| 3 | $(2,7),\,(3,1),\,(4,0),\,(5,6)$ |
| 4 | $(3,7),\,(4,2),\,(5,1),\,(6,0)$ |
| 5 | $(4,7),\,(5,3),\,(6,2),\,(0,1)$ |
| 6 | $(5,7),\,(6,4),\,(0,3),\,(1,2)$ |
| 7 | $(6,7),\,(0,5),\,(1,4),\,(2,3)$ |

In JSON format (each element is `[day1, day2, ..., day7]`, and each
day is `[boat1, boat2, boat3, boat4]`):

```json
[
  [[0,1,2,21,22,23],[3,4,5,18,19,20],[6,7,8,15,16,17],[9,10,11,12,13,14]],
  [[3,4,5,21,22,23],[0,1,2,6,7,8],[9,10,11,18,19,20],[12,13,14,15,16,17]],
  [[6,7,8,21,22,23],[3,4,5,9,10,11],[0,1,2,12,13,14],[15,16,17,18,19,20]],
  [[9,10,11,21,22,23],[6,7,8,12,13,14],[3,4,5,15,16,17],[0,1,2,18,19,20]],
  [[12,13,14,21,22,23],[9,10,11,15,16,17],[6,7,8,18,19,20],[0,1,2,3,4,5]],
  [[15,16,17,21,22,23],[12,13,14,18,19,20],[0,1,2,9,10,11],[3,4,5,6,7,8]],
  [[18,19,20,21,22,23],[0,1,2,15,16,17],[3,4,5,12,13,14],[6,7,8,9,10,11]]
]
```

---

## Verification

You can verify with this short Python script (also at
[`verify.py`](verify.py)):

```python
import itertools, json

N, TOTAL = 24, 276
def norm(p,q): return (min(p,q), max(p,q))

sched = json.loads('''[
  [[0,1,2,21,22,23],[3,4,5,18,19,20],[6,7,8,15,16,17],[9,10,11,12,13,14]],
  [[3,4,5,21,22,23],[0,1,2,6,7,8],[9,10,11,18,19,20],[12,13,14,15,16,17]],
  [[6,7,8,21,22,23],[3,4,5,9,10,11],[0,1,2,12,13,14],[15,16,17,18,19,20]],
  [[9,10,11,21,22,23],[6,7,8,12,13,14],[3,4,5,15,16,17],[0,1,2,18,19,20]],
  [[12,13,14,21,22,23],[9,10,11,15,16,17],[6,7,8,18,19,20],[0,1,2,3,4,5]],
  [[15,16,17,21,22,23],[12,13,14,18,19,20],[0,1,2,9,10,11],[3,4,5,6,7,8]],
  [[18,19,20,21,22,23],[0,1,2,15,16,17],[3,4,5,12,13,14],[6,7,8,9,10,11]]
]''')

pairs = set()
for day in sched:
    for boat in day:
        pairs.update(norm(p,q) for p,q in itertools.combinations(boat, 2))

assert len(pairs) == TOTAL
print(f"✓ All {TOTAL} pairs covered!")
```

Running it:

```
✓ All 276 pairs covered!
```

---

## What about 6 days?

I'll be honest — I don't know if 6 days is possible. The counting
arguments say it *could* be. Each rower would need to meet 3 people
three times and 1 person twice over the 6 days, forming a very specific
combinatorial structure (a 3-regular graph for the n=3 pairs, a perfect
matching for the n=2 pairs). I couldn't find such a schedule despite
extensive computational search.

If 6 is possible, the construction would be quite beautiful — probably
involving the Witt design $S(5,8,24)$ or the extended binary Golay code.
I'd love to see it if it exists.

But for now:

$$
\boxed{7\text{ days}}
$$

---

## Files

| File | Description |
|:---|---:|
| [`solution.md`](solution.md) | This write-up |
| [`verify.py`](verify.py) | Verification script |
| [`search3.py`](search3.py) | Early local search |
| [`search4.py`](search4.py) | Algebraic function exploration |
| [`affine_search3.py`](affine_search3.py) | Affine plane + local search |
| [`perm_search.py`](perm_search.py) | Permutation-based search |
| [`genetic.py`](genetic.py) | Genetic algorithm approach |
| [`seven_day.py`](seven_day.py) | The 7-day construction code |
| [`triangle_approach.py`](triangle_approach.py) | 8-triple analysis |