Maximising your Small Cases

(Xu Chen here) Hi everyone! Today I will be talking about 2018 C5, and my thought process while solving it.

(2018 C5) Let $k$ be a positive integer. The organising committee of a tennis tournament is to schedule the matches for $2k$ players so that every two players play once, each day exactly one match is played, and each player arrives to the tournament site the day of his first match, and departs the day of his last match. For every day a player is present on the tournament, the committee has to pay $1$ coin to the hotel. The organisers want to design the schedule so as to minimise the total cost of all players' stays. Determine this minimum cost.

This question appeared on NTST 2019 as Q10. After a rather long Q9 (I think I bashed the G4), I had about 2 hours to work on the problem.

Warning: spoilers ahead (duh!).

Initial thoughts:

• We want players to arrive late and depart early. These two are easy to achieve independently, but probably difficult to achieve together.
• If player $i$ arrives on day $a_i$ and departs on day $b_i$, then the total cost is $c(k) = \sum(b_i-a_i+1)$. Thus who arrives on which day is unimportant, only the (multi)set of days in which people arrive, and same for departures.
• Thus we instead let $a_1\leq a_2\leq\dots\leq a_{2k}$ be the days in which people arrive, and $b_1\leq b_2\leq\dots\leq b_{2k}$ be the days in which people depart. Note $a_i$ and $b_i$ need not refer to the same player.
• There is a trivial bound of $a_n\leq 1+\binom{n-1}{2}$, since the first $n-1$ players cannot play more than $\binom{n-1}{2}$ games, and a similar bound of $b_{2k-n+1}\geq\binom{2k}{2}-\binom{n-1}{2}$.
• This bound is probably the correct one for the first few $n$'s (about $k$? $k/2$?), but definitely not for all of them.
• Trying some small cases, $c(1) = 2, c(2) = 17$, and $c(3)$ onwards seem hard to determine easily.

What now? We need some idea of what the match arrangement is like beyond the first and last few. Let's look at the construction for $c(2)=17$. $$\begin{array}{c|c|c|c|c|c|c} \text{Match played:} & 12 & 13 & 23 & 14 & 24 & 34 \\ \hline \text{Arrivals/departures:} & a_1,a_2 & a_3 & & a_4,b_1 & b_2 & b_3,b_4 \end{array}$$ Already there's some freedom: Swapping matches 23 and 14 decreases both $a_4$ and $b_1$ by 1, but keeps the cost at 17. This suggests that for the "center" values, we should not be bounding single $a_i$'s or $b_j$'s, but rather differences of the form $b_j-a_i$.

Once again, there's a trivial bound of $a_{2k}\leq b_1$, since no one can leave before the last player arrives. Thus $b_1-a_{2k}\geq 0$.

What about $b_2-a_{2k-1}$? That's 3 in the construction above, and the matches in between are 13,23,14,24.

This should make sense: If the last two people to arrive are different from the first two people to leave, then they need $2^2=4$ matches between them, so $b_2-a_{2k-1}\geq 4-1=3$. On the other hand, if the same person arrives and leaves in that period of time, then that person must have played all $2k-1$ other people, giving $b_2-a_{2k-1}\geq 2k-2$, a much bigger bound.

Generalising this result should give $b_n-a_{2k-n+1}\geq n^2-1$ for sufficiently small $n$. To figure out exactly which $n$ this result holds for, we will actually need to work out both bounds explicitly. It turns out this holds for all $n\leq k$. Let's prove that.

Lemma. For each $n=1,2,\dots,k$, we have $b_n-a_{2k-n+1}\geq n^2-1$.

Proof. Let $A$ be the set of $n$ players that arrived the latest, and $B$ be the set of $n$ players that departed the earliest. Suppose $|A\cap B|=m$. Then, the following matches must have occurred between days $a_{2k-n+1}$ and $b_n$:

• Every two players in $A\cap B$ must have played each other, giving $\binom{m}{2}$ matches.
• Every player in $A\cap B$ must have played every player not in $A\cap B$, giving $m(2k-m)$ matches.
• Every player in $A\setminus B$ must have played every player in $B\setminus A$, giving $(n-m)^2$ matches.

Adding up gives $$\begin{align*} b_n-a_{2k-n+1} &\geq \binom{m}{2} + m(2k-m) + (n-m)^2 - 1 \\ &= n^2 - 1 + \frac{m(m-1+4k-4n)}{2}. \end{align*}$$ When $n\leq k$, the fraction on the right is always non-negative, giving our result.

Thus, $$\begin{align*} \sum_{i=1}^{2k} (b_i-a_i) &= \sum_{n=1}^{k} b_{2k-n+1} - \sum_{n=1}^k a_n + \sum_{n=1}^{k} (b_n-a_{2k-n+1}) \\ &\geq \sum_{n=1}^{k} \left[\binom{2k}{2}-\binom{n-1}{2}\right] - \sum_{n=1}^k \left[1+\binom{n-1}{2}\right]+ \sum_{n=1}^{k} \left(n^2-1\right) \\ &= \frac{k(k-1)(4k+5)}{2}. \end{align*}$$

At this point I ran out of time, so I quickly wrote down my current progress and hoped for a good partial.

I got 6/7. Turns out this is already the correct bound. Adding $2k$ gives $$c(k) = \sum_{i=1}^{2k} (b_i-a_i+1) \geq \frac{k(4k^2+k-1)}{2},$$ which is the correct answer. The construction follows pretty easily from the equality cases of the proof above, which are

• For $i=1,2,\dots,k$, the first $\binom{i-1}{2}$ matches are between the first $i-1$ players to arrive.
• For $i=1,2,\dots,k$, the last $\binom{i-1}{2}$ matches are between the last $i-1$ players to depart.
• The last $k$ players to arrive are disjoint from the first $k$ players to depart (since we always need $m=0$ for equality).
• For each $n=1,2,\dots,k$, the $n^2$ matches between days $a_{2k-n+1}$ and $b_n$ are between the last $n$ players to arrive and the first $n$ players to depart.

I'll leave the construction as an exercise.

All in all, I think this was a pretty cool question. Perhaps I will emphasize one point again: Observe how the construction for $k=2$ is used to motivate and guide the proof along. This is how you should be using your small cases: By looking for properties that generalise, and as a check for whether what you are trying to prove makes sense.