To solve this problem, we need to make two observations: one easy, one slighly more complicated.
The easy one: what happens if \(2k > n\)?
If more than half of all people have kitchen duty every day, it’s actually impossible to have two disjoint kitchen crews – there’s not enough people for that. And therefore this condition is satisfied automatically and we only have to worry about the other one: no crew can repeat. Clearly, then the optimal answer must be that there were \(d = {n\choose k}\) days – one with each possible \(k\)-element subset of the set of our \(n\) people.
The harder observation handles the opposite case. This observation was first proved by Erdős, Ko, and Rado and it’s sometimes called the sunflower lemma. We claim that whenever \(2k\leq n\), there is always an optimal solution in which there is a person who has kitchen duty on all \(d\) days. This will give us both the solution size and an easy construction of one optimal solution.
Below we present one cute proof of this claim.
We will show an upper bound on the size of the optimal solution: for \(2k\leq n\) the optimal solution contains at most \(k/n\) out of all possible \(k\)-person kitchen crews.
Let’s look at all kitchen crews that are formed by \(k\) people with (cyclically) consecutive numbers. E.g., for \(k=3\) these would be \((0,1,2)\), \((1,2,3)\), \((2,3,4)\), and so on until \((n-3,n-2,n-1)\), \((n-2,n-1,0)\), and \((n-1,0,1)\). In this list we have exactly \(n\) crews. And if we try to include many of them into a valid solution, we’ll quickly discover that there is no way to take more than \(k\) of them.
We can now formulate and prove a more general version of this fact.
Lemma: Let \(p\) be any permutation of the numbers from \(0\) to \(n-1\). Consider the \(n\) kitchen crews of the form \(( p_{i}, \dots, p_{ (i+k-1) \bmod n} )\). We claim that any valid solution can contain at most \(k\) out of these \(n\) kitchen crews.
Proof: Without loss of generality, assume that \((p_0, \dots, p_{k-1})\) is one of the selected kitchen crews. Each of the other selected crews must have a non-empty intersection with this one. Among our other \(n-1\) crews there are exactly \(2(k-1)\) such crews: the \((k-1)\) preceding and the \((k-1)\) following our crew in their cyclic order.
These \(2(k-1)\) crews can now be divided into \(k-1\) pairs such that in each pair the two crews are disjoint. To do this, we will pair the crew that ends with \(p_i\) with the crew that begins with \(p_{i+1}\). Once we do that, we see that from each of the \(k-1\) pairs each valid solution can contain at most one crew, which proves the lemma.
(For pedants: note that the assumption \(2k\leq n\) ensures that all crews we mention are mutually distinct, and that within each pair the two crews are actually disjoint.)
We can now finish the proof of the original claim by using a probabilistic argument. (If you dislike real numbers, the argument can quite easily be turned into a counting one.)
Theorem: Whenever \(2k\leq n\), the optimal solution consist of at most \(k/n\) of all possible \(k\)-person kitchen crews.
Proof: Suppose we have an optimal solution. We can now pick a \(k\)-person crew uniformly at random and ask the question “what is the probability that this crew appears in the solution?”.
On one hand, this probability is equal to (the size of the optimal solution) divided by (the number of all possible kitchen crews).
On the other hand, one particular way in which we can select a \(k\)-person crew uniformly at random looks as follows:
And now clearly once we fix \(p\), the probability that the choice of \(i\) will select a good crew will always be at most \(k/n\), q.e.d.
We now know that for \(2k\leq n\) the optimal solution has at most \(\frac{k}{n} {n\choose k}\) elements. It’s easy to see that \(\frac{k}{n} {n\choose k}\) can be simplified to \({n-1\choose k-1}\). Hence, if we can find a solution of the size \({n-1 \choose k-1}\), it will have to be optimal.
And the solution type we mentioned earlier has precisely this property. If we pick any one person and take all possible kitchen crews that contain this particular person, for each day we need to select which \(k-1\) out of the \(n-1\) remaining people will join the special one. Thus, this construction gives us a solution of size \({n-1\choose k-1}\), and therefore this must be the optimal value of \(d\).
