The Universe of Disco

Concerts

Obviously, no more than six concerts are required. (I have a new contribution to the long-debated meaning of the mathematical jargon term "obviously": if my six-year-old daughter Katara could figure out the answer, so can you.) And an easy argument shows that four are necessary: let's say that when a musician views another, that is a "viewing event"; we need to arrange at least 5×6 = 30 viewing events. A concert that has p performers and 6-p in the audience arranges p(6 - p) events, which must be 5, 8, or 9. Three concerts yield no more than 27 events, which is insufficient. So there must be at least 4 concerts, and we may as well suppose that each concert has three musicians in the audience and three onstage, to maximize the number of events at 9·4 = 36. (It turns out there there is no solution otherwise, but that is a digression.)

Each musician must attend at least 2 concerts, or else they would see only 3 other musicians onstage. But 6 musicians attending 2 concerts each takes up all 12 audience spots, so every musician is at exactly 2 concerts. Each musician thus sees exactly six musicians onstage, and since five of them must be different, one is a repeat, and the viewing event is wasted. We knew there would be some waste, since there are 36 viewing avents available and only 30 can be useful, but now we know that each spectator wastes exactly one event.

A happy side effect of splitting the musicians evenly between the stage and the audience in every concert is that we can exploit the symmetry: if we have a solution to the problem, then we can obtain a dual solution by exchanging the performers and the audience in each concert. The conclusion of the previous paragraph is that in any solution, each spectator wastes exactly one event; the duality tells us that each performer is the subject of exactly one wasted event.

Now suppose the same two musicians, say A and B, perform together twice. We know that some spectator must see A twice; this spectator sees B twice also, this wasting two events. But each spectator wastes only one event. So no two musicians can share the stage twice; each two musicians share the stage exactly once. By duality, each two spectators are in the same audience together exactly once.

So we need to find four 3-sets of the elements { A, B, C, D, E, F }, with each element appearing in precisely two sets, and such that each two sets have exactly one element in common.

Or equivalently, we need to find four triangles in K₄, none of which share an edge.

The solution is not hard to find:

	1	2	3	4
On stage	A B C	C D E	E F A	B D F
In audience	D E F	A B F	B C D	A C E

If you generalize these arguments to 2m musicians, you find that there is a lower bound of $$\left\lceil{4m^2 - 2m \over m^2 }\right\rceil$$ concerts, which is 4. And indeed, even with as few as 4 musicians, you still need four concerts. So it's tempting to wonder if 4 concerts is really sufficient for all even numbers of musicians. Consider 8 musicians, for example. You need 56 viewing events, but a concert with half the musicians onstage and half in the audience provides 16 events, so you might only need as few as 4 concerts to provide the necessary events.

The geometric formulation is that you want to find four disjoint K₄s in a K₈; or alternatively, you want to find four 4-element subsets of { 1,2,3,4,5,6,7,8 }, such that each element appears in exactly two sets and no two elements are in the same. There seemed to be no immediately obvious reason that this wouldn't work, and I spent a while tinkering around looking for a way to do it and didn't find one. Eventually I did an exhaustive search and discovered that it was impossible.

But the tinkering and the exhaustive search were a waste of time, because there is an obvious reason why it's impossible. As before, each musician must be in exactly two audiences, and can share audiences with each other musician at most once. But there are only 6 ways to be in two audiences, and 8 musicians, so some pair of musicians must be in precisely the same pair of audiences, this wastes too many viewing events, and so there's no solution. Whoops!

It's easy to find solutions for 8 musicians with 5 concerts, though. There is plenty of room to maneuver and you can just write one down off the top of your head. For example:

	1	2	3	4	5
On stage	E F G H	B C D H	A C D F G	A B D E G	A B C E F H
In audience	A B C D	A E F G	B E H	C F H	D G

[ Addendum: For n = 1…10 musicians, the least number of concerts required is 0, 2, 3, 4, 4, 4, 5, 5, 5, 5; beyond this, I only have bounds. ]

[Other articles in category /math] permanent link