4 Boats (GPT 5.5)
Weirdly GPT didn’t include the code the first time around, and I had to prompt it to add it to the end of the blog.
It was somewhat implied in the statement.txt that that’s what I wanted. But it wasn’t explicit.
The minimum number of days is:
$$ \boxed{6} $$
There are $24$ participants, so there are
$$ {24 \choose 2}=276 $$
pairs that must be covered. On any one day, each of the four boats contains $6$ people, so that day covers
$$ 4{6 \choose 2}=4\cdot 15=60 $$
pairs. This immediately gives
$$ d \ge \left\lceil \frac{276}{60} \right\rceil = 5. $$
That bound is not strong enough by itself. Five days would have $5\cdot 60=300$ pair-slots, only $24$ more than the $276$ pairs we need, and the structure of the daily partitions forces many more overlaps than that.
Why five days cannot work
Assume, for contradiction, that five days are enough. For each pair of participants ${x,y}$, let $m_{xy}$ be the number of days on which they share a boat. Since the schedule is assumed to work, every $m_{xy}\ge 1$.
Fix one participant $x$. Across five days, $x$ sits with $5$ other people per day, for $25$ partner-incidences total. There are only $23$ other participants, and every one of them must appear at least once with $x$. Therefore
$$ \sum_{y\ne x}(m_{xy}-1)=25-23=2. $$
Now count a different thing: a repeated pair of people together with the two days on which that pair was repeated. Let
$$ T=\sum_{x<y}{m_{xy}\choose 2}. $$
This counts, over all pairs of days, how many participant-pairs are together on both of those days.
For a fixed participant $x$, the sum
$$ \sum_{y\ne x}{m_{xy}\choose 2} $$
is largest when the two excess incidences for $x$ are concentrated on one other participant. In that case it is ${3\choose 2}=3$. Hence
$$ 2T \le 24\cdot 3, $$
so
$$ T\le 36. $$
But any two days must overlap in at least $8$ pairs. To see this, compare one boat from the first day with the four boats from the second day. Its $6$ people are split among four boats, and the quantity
$$ \sum {n_i\choose 2} $$
is minimized when the split is as even as possible: $2,2,1,1$. That still gives $1+1=2$ repeated pairs for that boat. There are four boats on the first day, so any pair of days has at least $4\cdot 2=8$ common participant-pairs.
With five days there are ${5\choose 2}=10$ pairs of days, so this same quantity must satisfy
$$ T\ge 10\cdot 8=80. $$
This contradicts $T\le 36$. Therefore five days are impossible.
Since the counting bound showed only that at least five days are needed, this proves that at least six days are needed.
A six-day construction
Here is an explicit six-day schedule. Participants are numbered $0$ through $23$. Each outer array element is one day, and each day has four boats of six participants.
[
[[0, 6, 11, 13, 18, 23], [7, 8, 9, 10, 19, 21], [2, 12, 14, 15, 16, 17], [1, 3, 4, 5, 20, 22]],
[[2, 3, 10, 11, 21, 22], [0, 4, 6, 9, 13, 15], [8, 14, 17, 18, 19, 20], [1, 5, 7, 12, 16, 23]],
[[0, 2, 6, 7, 13, 20], [4, 10, 12, 16, 18, 21], [3, 8, 15, 19, 22, 23], [1, 5, 9, 11, 14, 17]],
[[4, 6, 8, 14, 17, 19], [2, 7, 9, 11, 15, 23], [0, 10, 12, 16, 20, 21], [1, 3, 5, 13, 18, 22]],
[[3, 6, 9, 12, 16, 22], [10, 13, 14, 17, 21, 23], [4, 7, 11, 15, 18, 20], [0, 1, 2, 5, 8, 19]],
[[1, 5, 6, 10, 15, 21], [0, 3, 7, 14, 17, 22], [8, 11, 12, 13, 16, 19], [2, 4, 9, 18, 20, 23]]
]
Verification
I verified the construction with this short script.
from itertools import combinations
schedule = [
[[0, 6, 11, 13, 18, 23], [7, 8, 9, 10, 19, 21], [2, 12, 14, 15, 16, 17], [1, 3, 4, 5, 20, 22]],
[[2, 3, 10, 11, 21, 22], [0, 4, 6, 9, 13, 15], [8, 14, 17, 18, 19, 20], [1, 5, 7, 12, 16, 23]],
[[0, 2, 6, 7, 13, 20], [4, 10, 12, 16, 18, 21], [3, 8, 15, 19, 22, 23], [1, 5, 9, 11, 14, 17]],
[[4, 6, 8, 14, 17, 19], [2, 7, 9, 11, 15, 23], [0, 10, 12, 16, 20, 21], [1, 3, 5, 13, 18, 22]],
[[3, 6, 9, 12, 16, 22], [10, 13, 14, 17, 21, 23], [4, 7, 11, 15, 18, 20], [0, 1, 2, 5, 8, 19]],
[[1, 5, 6, 10, 15, 21], [0, 3, 7, 14, 17, 22], [8, 11, 12, 13, 16, 19], [2, 4, 9, 18, 20, 23]],
]
covered = set()
for day in schedule:
assert len(day) == 4
flat = [person for boat in day for person in boat]
assert sorted(flat) == list(range(24))
for boat in day:
assert len(boat) == 6
for pair in combinations(boat, 2):
covered.add(tuple(sorted(pair)))
assert len(covered) == 276
print("all pairs covered")
Search notes
The first useful method was the raw counting lower bound: $276$ required pairs and $60$ pairs per day. It only proves that at least five days are needed.
The next method was the overlap count above. It rules out the five-day case by showing that five daily partitions would be forced to overlap too much.
I also tried an algebraic construction: label participants by elements of a group of order $24$, then use cosets of subgroups of size $6$ as the boats. This would have made each day a clean partition automatically. The abelian groups of order $24$ did not provide six size-$6$ subgroups whose union covered all possible differences, so that route did not give a schedule.
The final construction came from a local search. I represented a schedule as six partitions of the $24$ participants and optimized the number of uncovered pairs, using swaps inside individual days. Once the search reached zero uncovered pairs, the verification script above checked the result directly.
Here is the construction search code I used, with only minor formatting cleanup. It is randomized, so a particular run may take a different number of restarts.
import math
import random
import time
from itertools import combinations
N = 24
BOAT_SIZE = 6
BOATS_PER_DAY = 4
DAYS = 6
pairs = []
pair_index = {}
for i in range(N):
for j in range(i + 1, N):
pair_index[(i, j)] = len(pairs)
pairs.append((i, j))
def pidx(a, b):
if a > b:
a, b = b, a
return pair_index[(a, b)]
def normalize(schedule):
return [[sorted(boat) for boat in day] for day in schedule]
def random_schedule():
schedule = []
for _ in range(DAYS):
people = list(range(N))
random.shuffle(people)
schedule.append(
[people[i * BOAT_SIZE : (i + 1) * BOAT_SIZE] for i in range(BOATS_PER_DAY)]
)
return schedule
def build_counts(schedule):
counts = [0] * len(pairs)
for day in schedule:
for boat in day:
for a, b in combinations(boat, 2):
counts[pidx(a, b)] += 1
return counts
def uncovered_pairs(counts):
return [i for i, count in enumerate(counts) if count == 0]
def build_positions(schedule):
positions = []
for day in schedule:
day_positions = [None] * N
for boat_number, boat in enumerate(day):
for place, person in enumerate(boat):
day_positions[person] = (boat_number, place)
positions.append(day_positions)
return positions
def swap_delta(schedule, positions, counts, day, boat_a, place_a, boat_b, place_b, apply):
if boat_a == boat_b:
return 0
x = schedule[day][boat_a][place_a]
y = schedule[day][boat_b][place_b]
removed = []
added = []
for z in schedule[day][boat_a]:
if z != x:
removed.append(pidx(x, z))
added.append(pidx(y, z))
for z in schedule[day][boat_b]:
if z != y:
removed.append(pidx(y, z))
added.append(pidx(x, z))
delta = 0
for p in removed:
if counts[p] == 1:
delta += 1
for p in added:
if counts[p] == 0:
delta -= 1
if apply:
for p in removed:
counts[p] -= 1
for p in added:
counts[p] += 1
schedule[day][boat_a][place_a], schedule[day][boat_b][place_b] = y, x
positions[day][x] = (boat_b, place_b)
positions[day][y] = (boat_a, place_a)
return delta
def improve(schedule, seconds):
positions = build_positions(schedule)
counts = build_counts(schedule)
uncovered = len(uncovered_pairs(counts))
temperature = 0.5
start = time.time()
while time.time() - start < seconds:
if uncovered == 0:
return True, normalize(schedule)
candidates = []
# Usually target a currently uncovered pair and try to put it together
# on one of the six days by swapping one person between boats.
if random.random() < 0.8:
pair_number = random.choice(uncovered_pairs(counts))
a, b = pairs[pair_number]
for day in range(DAYS):
boat_a, place_a = positions[day][a]
boat_b, place_b = positions[day][b]
if boat_a == boat_b:
continue
for place, z in enumerate(schedule[day][boat_a]):
if z != a:
delta = swap_delta(
schedule, positions, counts, day, boat_a, place, boat_b, place_b, False
)
candidates.append((delta, day, boat_a, place, boat_b, place_b))
for place, z in enumerate(schedule[day][boat_b]):
if z != b:
delta = swap_delta(
schedule, positions, counts, day, boat_b, place, boat_a, place_a, False
)
candidates.append((delta, day, boat_b, place, boat_a, place_a))
if candidates:
candidates.sort(key=lambda item: item[0])
delta, day, boat_a, place_a, boat_b, place_b = candidates[0]
else:
day = random.randrange(DAYS)
boat_a, boat_b = random.sample(range(BOATS_PER_DAY), 2)
place_a = random.randrange(BOAT_SIZE)
place_b = random.randrange(BOAT_SIZE)
delta = swap_delta(
schedule, positions, counts, day, boat_a, place_a, boat_b, place_b, False
)
if delta <= 0 or random.random() < math.exp(-delta / max(temperature, 0.01)):
swap_delta(schedule, positions, counts, day, boat_a, place_a, boat_b, place_b, True)
uncovered += delta
temperature = max(0.03, temperature * 0.99995)
return False, normalize(schedule)
deadline = time.time() + 180
restart = 0
while time.time() < deadline:
restart += 1
ok, schedule = improve(random_schedule(), 20)
if ok:
print("found on restart", restart)
print(schedule)
break
else:
print("no construction found in time")