quirino.net

4 Boats - Solutions and AI evaluations

Date

The minimum number of days is 6.

This problem is interesting because both the lower bound and the construction are tricky to find. It’s easy to get quite close: the 5-day lower bound requires a single sentence and a 7-day schedule can be constructed by hand or easily found by code.

But getting to 6 is quite a bit harder on both sides.

Why 5 days aren’t enough

Assume for contradiction that 5 days suffice. Let $A$ be a $24 \times 24$ matrix where $A_{ij}$ is the number of times person $i$ and person $j$ share a boat. We consider person $i$ to always “meet” themselves, so the diagonal entries are all 5.

Let $B_i$ be the matrix of meetings on day $i$. Then $A = \sum_{i=1}^{5} B_i$.

The rank of each $B_i$ is 4, because the rows of people in the same boat are identical, so there are only 4 distinct row vectors. Thus the rank of $A$ is at most $4 \cdot 5 = 20$.

Let $J$ be the $24 \times 24$ all-ones matrix. $J$ has rank 1, so $A - J$ has rank at most 21.

However, if all pairs have met, $A$’s entries are tightly constrained. The diagonals are all 5, and since each person has $5 \times 5 = 25$ meetings with other people, all non-diagonal entries of $A$ are 1, except for a 3 or two 2s in each row.

So $A - J$ has 4 on the diagonal, and each row has either two 1s or a single 2 in off-diagonal positions (the rest being zeroes). This means $A - J$ is strictly diagonally dominant and thus invertible (Lévy–Desplanques theorem). So it has full rank 24, contradicting rank $\leq 21$.

This proof is by /u/ProudHaskeller on Reddit, editorialized by me.

Finding a 6-day construction

I wrote some C++ code that finds constructions for 6 days. It usually finds the solution in under a second.

The idea is:

  1. Assign people to boats completely randomly.
  2. Randomly pick two people on a given day. If swapping them increases the number of covered pairs, swap them.
  3. Every 100k iterations, fully shuffle a random day.

The third step was a heuristic I introduced after finding that the second step frequently got stuck at a local minimum, and that less extreme forms of trying to get it unstuck didn’t work (like allowing with a certain probability moves that worsen the score).

I wish I had a more satisfying explanation for why this works, but I just tried lots of different things.

AI Evaluations

I also gave this problem to several AI models. Each was given this statement.txt file in an empty directory and prompted: Follow the instructions in the statement.txt file.

I understand all models all arrived at the lower bound via the same argument, different from the one above. I suggest reading GPT 5.5’s entry, since it’s quite clear.

I haven’t carefully verified the proofs.