K2) Let $n \geq 4$ and $k, d \geq 2$ be natural numbers with $k \cdot d \leq n$. The $n$ participants in the Mathematical Olympiad are sitting around a round table waiting for Patrick. When Patrick shows up, he doesn't like the situation at all, as the rules of social distancing are not being observed. So he selects $k$ of the $n$ participants who are allowed to stay and sends everyone else out of the room so that there are at least $d-1$ empty seats between every two of the remaining $k$ participants. How many opportunities does Patrick have to do this, assuming all seats were initially occupied?

Answer: $\frac{n}{k}\binom{n-k d+k-1}{k-1}$ or equivalent expressions.
Solution 1 (Surjective $k$-to-1 mapping): First, let's number the people at the table clockwise from 1 to $n$, with the 1 person chosen at random. We will now count how many combinations there are in which person 1 is chosen. Note that any such possibility simply corresponds to choosing $k$ 'distances' between the chosen participants. The given condition is simply that each such 'distance' should be greater than $d$. So we want to count the possibilities of choosing a group of $k$ distances so that they are all greater than $d$ and add up to $n$. This can be counted in several ways:

- For example, you can imagine a small table surrounded by $n-k d+k$ chairs, where the chair with the number 1 is occupied and you have to select $k-1$ chairs that still need to be occupied. You can then insert $d-1$ chairs between all two consecutive people to obtain a final configuration. So here you had $\binom{n-k d+k-1}{k-1}$ possibilities to do this.
- In other words, we can also say that the problem here is the same as if we want to distribute $n$ equal candies to $k$ children so that each child gets at least $d$ candies, which was covered in the script. Here we can simply forget the $k d$ candies to fulfill the condition, which means that we still have $n-k d$ candies to distribute. Here you also get $\binom{n-k d+k-1}{k-1}$ ways to do this.

However, up to now we have assumed that person 1 is always chosen. So now we have to consider all 'rotations' (by considering a person other than the arbitrary 1 person). If we were to simply add up the possibilities for all rotations, we would have counted each 'real' configuration $k$ times (1 time for each of the $k$ chosen persons). So we get the final answer $\frac{n}{k}\binom{n-k d+k-1}{k-1}$. If this solution was too confusing, you can look at the last step differently: Consider the original problem where one of the k persons is an imposter. the number of possibilities can be calculated as described above. You start with the imposter and look at the distances between the chosen persons, which gives you $\binom{n-k d+k-1}{k-1}$ possibilities for each of the n possible imposters. You can also look at this number differently. For each possibility of the original problem, there are k possibilities to choose the imposter. Thus, the number of combinations of the original problem is equal to $n\binom{n-k d+k-1}{k-1} \cdot \frac{1}{k}$