Here's a riddle I came across recently:
There’s a group of six friends who are all musicians. One day, they decide to have a few performances between themselves so that they can hear each other one play, each one with some of them playing and the rest in the audience listening. What’s the minimum number of performances they need so that each of them hears all of the others play from the audience?
I have the solution: 4 performances. They are:
1:$P123 \, L456$
2:$P561 \, L234$
3:$P345 \, L612$
4:$P624 \, L135$
We came to that answer without using math, but to me it feels like there is a simple way to find the number of performances using math. Is that the case? What would the equation be?
Define a $6\times6$ matrix as follows $$ \mathscr{M}^{(p)}_{ij}=\begin{cases} 0&\text{if i=j}\\ 1&\text{if i-th musician has heard j-th musician play after p-th performance}\\ 2&\text{if i-th musician is yet to hear j-th musician play after p-th performance} \end{cases} $$ The goal is to make every off-diagonal entry $1$ with least $p$. $\mathscr{M}^{(0)}$ has $30$ off-diagonal entries that aren't $1$. So we have to change $30$ entries. If during one performance there are $x$ performers and $y$ listeners, the maximum number of entries that can be changed due to that performance is $xy$ in which case none of the listeners had listened to any of the performers before. $$ x+y=6\implies x^2+y^2+2xy=36\implies4xy\le36\text{ by AM-GM}\\ \implies xy\le9 $$ So we need at least $\left\lceil{30\over9}\right\rceil=4$ performamces. The arrangement of the performances in the OP shows that $4$ indeed gets the job done. Replacing $6$ with $n$ we see the lower bound on the required number of performances achieved this way is $$\left\lceil{n(n-1)\over{n^2\over4}}\right\rceil=\left\lceil{4(1-{1\over n})}\right\rceil=\begin{cases} 4,& n>4\\ 3,& 3\le n\le4\\ 2,& n=2 \end{cases}$$ And to get as close to this lower bound as possible we need to choose $x,y$ in such a way that $xy$ is as close to ${n^2\over4}$ as possible which means for even $n$ we should choose $x=y={n\over2}$ and for odd $n$ we should have $\{x,y\}=\{{n+1\over2},{n-1\over2}\}$.