4 Boats - quirino.net

24 people are at a rowing meet.<br>They have 4 boats, each fitting exactly 6 people.<br>Over several days,<br>all participants are assigned to boats,<br>with assignments possibly changing daily.

You&rsquo;re responsible for allocating the members into boats,<br>and your goal is to ensure each of the<br>$\binom{24}{2} = 276$ unique pairs of participants<br>share a boat on at least one day.

What&rsquo;s the minimum number of days the rowing meet<br>must last for this to be possible?

Some pointers

Lower bound

Person 1 must meet 23 other people.<br>Since they meet at most 5 new people each day<br>we need at least 5 days .<br>But is 5 days enough?

Construct by hand

An obvious construction takes 276 days :<br>on each day, focus only on making a specific pair of people meet.

You can still do much better by hand. The construction above uses only a pair of seats.<br>Try making use of Symmetry or &ldquo;gluing&rdquo; some people together to reduce your problem.

Write code

Writing code for this kind of problem is a lot of fun.<br>Here are some heuristics to try:

Each day assign boats completely randomly, repeat until all pairs have met.

Construct assignments person by person, always picking someone the current person hasn&rsquo;t met yet.

To determine if a certain number of days is enough, create an initial assignment and repeatedly make swaps that improve your construction (in the vein of Hill Climbing or Simulated Annealing)

Solutions and AI Evaluations

A couple small spoilers regarding the difficulty of this problem:

Proving the lower bound is a non-trivial math exercise. I&rsquo;m aware of two different proofs.

I&rsquo;m only aware of constructions of the correct answer through code.

To avoid spoiling the correct answer, I placed the solutions on a separate page.<br>I also evaluate how various AI models fare in trying to solve this problem.