Round table and microphones, a pigeonhole problem

Question

20 people are sitting around a table. 9 of them want to give a speech, and there are 9 microphones on the table in front of 9 random people. The microphones are fixed but we can turn the table.How can we show that no matter how the microphones are distributed at first, we can turn the table in a way that most of the speakers get a microphone at the same time.

Answer 1

There are 20 possible rotations or configurations of the table. Let $M(i, j)$ be equal to $1$ if the $i$-th speaker is in front of a microphone when the table is positioned in the $j$-th rotation, and to $0$ otherwise. For each speaker, there are exactly $9$ rotations where she is in front of a microphone: that is, $\sum_{j=1}^{20} M(i, j) = 9$. Adding this over all $9$ speakers, we have $\sum_{i=1}^9 \sum_{j=1}^{20} M(i, j) = 81$. Switching the order of summation, $\sum_{j=1}^{20} \sum_{i=1}^9 M(i, j) = 81$. But $\sum_{i=1}^9 M(i, j)$ for a fixed $j$ is precisely the number of speakers in front of a microphone in the $j$-th configuration: if that number were $\leq 4$ for all configurations, then the sum would be $\leq 80$. Therefore there is a configuration with at least $5$ speakers in front of a microphone.