$8$ singers take part in a festival. The organiser wants to plan $m$ concerts. For every concert there are $4$ singers who go on stage, with the restriction that the times of which every two singers go on stage in a concert are all equal. Find a schedule that minimises $m$.
Problem
Source: CMO-1996-4
Tags: combinatorics unsolved, combinatorics
06.01.2006 15:00
Assume the singers are $A,B,C,D,E,F,G,H$ Let $S_{A,B}$ be the numbers of times $A$ and $B$ go on stage together. Let $S = \sum S_{A,B}$ for all possible pairs of singers. (There are C(8,2) = 28 pairs) Since the times of which every two singers go on stage in a concert are all same, we have that $S = 28S_{A,B}$ On the other hand, in each concert six pairs of singers go on stage together. So, $S = 6m$ So $28S_{A,B} = 6m$ $14S_{A,B} = 3m$ $m = \frac{14S_{A,B}}{3}$ $m\geq 14$ 14 concerts is possible: $(A,B,C,D),(A,B,E,F),(A,B,G,H),(C,D,E,F),$ $(C,D,G,H),(E,F,G,H),(A,C,E,G),(B,D,F,H)$ $,(A,C,F,H),(B,D,E,G),(A,D,E,H),(B,C,F,G),(A,D,F,G),(B,C,E,H)$
19.06.2022 01:06
The minimum is 14. Let the equal quantity be $k$, such that $${8 \choose 2} \cdot k = {6 \choose 2} \cdot m \iff 14k = 3m,$$which implies $14 \mid m$ and $m \geq 14$. Now we give a construction for 14. Label the singers $a_1, a_2, \cdots, a_8$ in some order. Consider the set of constructions $(a_1, a_{2+i}, a_{3+i}, a_{5+i})$ and $(a_{2+i}, a_{3+i}, a_{4+i}, a_{6+i})$ for $0 \leq i \leq 6$. Indeed, in this construction, each pair of singers appears on-stage simultaneously precisely three times, so we are done.