2

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?

Ben Kane
  • 123
  • 6
  • A binomial coefficient would give you the maximum number of performances that are possible. Specifically ${6\choose3}=20$. To reduce that, you could observe that each person has to be in the audience twice to hear everyone else, and each person has someone who must be heard twice (pigeon-hole principle). From there, I am not sure. I think there is a quick way, but I have to think about it. – Terra Hyde Jul 17 '15 at 15:21
  • Note that you don't have to have 3 playing and listening at a time. Any number can play or listen. – Ben Kane Jul 17 '15 at 15:23

1 Answers1

1

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}\}$.

Jack's wasted life
  • 8,849