2
$\begingroup$

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 maths, but to me it feels like there is a simple way to find the number of performances using maths. Is that the case? What would the equation be?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Terra Hyde Jul 17 '15 at 15:21
  • $\begingroup$ Note that you don't have to have 3 playing and listening at a time. Any number can play or listen. $\endgroup$ – Ben Kane Jul 17 '15 at 15:23
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That abs(30/9) should be abs(36/9), correct? $\endgroup$ – Ben Kane Jul 17 '15 at 20:44
  • $\begingroup$ nope that's ceilng function $\endgroup$ – Jack's wasted life Jul 17 '15 at 20:44
  • $\begingroup$ oh yea. reading too fast. thanks. $\endgroup$ – Ben Kane Jul 17 '15 at 20:45
  • $\begingroup$ I don't fully understand the matrix part. Are you able to go more in-depth with that? $\endgroup$ – Ben Kane Jul 17 '15 at 20:46
  • $\begingroup$ The matrix part isn't important at all. I'm not using any properties of the matrix. $0,1,2$ are completely arbitrary. I used the matrix to mathematically express the problem. That's it. If you want you can think that each of the $6$ musician needs to listen $5$ other musicians. So we need to have $6\times5=30$ different individual listens... $\endgroup$ – Jack's wasted life Jul 17 '15 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.