Maths Olympiad Prep

Library / /108 of 128

Combinatorics Difficulty 6.5 National Olympiad Prove it Philippines

Problem:

Twelve students participated in a theater festival consisting of nn different performances. Suppose there were six students in each performance, and each pair of performances had at most two students in common. Determine the largest possible value of nn.

Solution

Solution:

We label the students by 1,2,,121,2, \ldots, 12 and the performances by the subsets P1,,PnP_{1}, \ldots, P_{n} of {1,,12}\{1, \ldots, 12\}. Then the problem now reduces to finding the maximum value of nn such that

(a) Pi=6|P_{i}|=6 for all 1in1 \leq i \leq n, and

(b) PiPj2|P_{i} \cap P_{j}| \leq 2 for all 1i<jn1 \leq i<j \leq n.

We make a 12×n12 \times n {0,1}\{0,1\}-matrix MM whose entries are defined as follows:
Mij={1 if student i plays in performance Pj0 if student i does not play in performance Pj M_{ij}= \begin{cases}1 & \text{ if student } i \text{ plays in performance } P_{j} \\ 0 & \text{ if student } i \text{ does not play in performance } P_{j}\end{cases}
For each i{1,,12}i \in \{1, \ldots, 12\}, let ri=j=1nMijr_{i}=\sum_{j=1}^{n} M_{ij} be the number of times ii appears in the sets P1,,PnP_{1}, \ldots, P_{n}. Then, by double-counting, we have i=112ri=6n\sum_{i=1}^{12} r_{i}=6 n. Let R\mathcal{R} be the set of all unordered pairs of 1's that lie in the same row. Counting by rows, we see that in the iith row, there are rir_{i} 1's and thus (ri2)\binom{r_{i}}{2} pairs. Thus, R=i=112(ri2)|\mathcal{R}|=\sum_{i=1}^{12}\binom{r_{i}}{2}. Counting by columns, we note that for any two columns, there are at most 2 pairs of 1's among these columns, so R2(n2)=n(n1)|\mathcal{R}| \leq 2\binom{n}{2}=n(n-1). Thus,
i=112(ri2)n(n1)i=112ri2i=112ri2n(n1)i=112ri22n2+4n. \sum_{i=1}^{12}\binom{r_{i}}{2} \leq n(n-1) \Longrightarrow \sum_{i=1}^{12} r_{i}^{2}-\sum_{i=1}^{12} r_{i} \leq 2 n(n-1) \Longrightarrow \sum_{i=1}^{12} r_{i}^{2} \leq 2 n^{2}+4 n.
By the Cauchy-Schwarz inequality,
36n2=(i=112ri)212i=112ri2=24n2+48n 36 n^{2}=\left(\sum_{i=1}^{12} r_{i}\right)^{2} \leq 12 \sum_{i=1}^{12} r_{i}^{2}=24 n^{2}+48 n
which implies that n4n \leq 4. For n=4n=4, we have the following specific sets P1,,P4P_{1}, \ldots, P_{4} satisfying the conditions of the problem:
P1={1,2,3,4,5,6},P2={1,3,7,8,11,12}P3={2,4,7,8,9,10},P4={5,6,9,10,11,12} \begin{array}{cl} P_{1}=\{1,2,3,4,5,6\}, & P_{2}=\{1,3,7,8,11,12\} \\ P_{3}=\{2,4,7,8,9,10\}, & P_{4}=\{5,6,9,10,11,12\} \end{array}
Hence, the maximum value of nn is n=4n=4.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.