Maths Olympiad Prep

Library / Asia Pacific Mathematics Olympiad (APMO) competition problems /3 of 3

Asia Pacific Mathematics Olympiad (APMO) competition problems

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

In a circus, there are nn clowns who dress and paint themselves up using a selection of 12 distinct colours. Each clown is required to use at least five different colours. One day, the ringmaster of the circus orders that no two clowns have exactly the same set of colours and no more than 20 clowns may use any one particular colour. Find the largest number nn of clowns so as to make the ringmaster's order possible.

Solution

Let CC be the set of nn clowns. Label the colours 1,2,3,…,121,2,3, \ldots, 12. For each i=1,2,…,12i=1,2, \ldots, 12, let EiE_{i} denote the set of clowns who use colour ii. For each subset SS of {1,2,…,12}\{1,2, \ldots, 12\}, let ESE_{S} be the set of clowns who use exactly those colours in SS. Since S≠S′S \neq S^{\prime} implies ES∩ES′=∅E_{S} \cap E_{S^{\prime}}=\emptyset, we have
∑S∣ES∣=∣C∣=n, \sum_{S}\left|E_{S}\right|=|C|=n,
where SS runs over all subsets of {1,2,…,12}\{1,2, \ldots, 12\}. Now for each ii,
ES⊆Ei if and only if i∈S, E_{S} \subseteq E_{i} \quad \text{ if and only if } \quad i \in S,
and hence
∣Ei∣=∑i∈S∣ES∣. \left|E_{i}\right|=\sum_{i \in S}\left|E_{S}\right| .
By assumption, we know that ∣Ei∣≤20\left|E_{i}\right| \leq 20 and that if ES≠∅E_{S} \neq \emptyset, then ∣S∣≥5|S| \geq 5. From this we obtain
20×12≥∑i=112∣Ei∣=∑i=112(∑i∈S∣ES∣)≥5∑S∣ES∣=5n. 20 \times 12 \geq \sum_{i=1}^{12}\left|E_{i}\right|=\sum_{i=1}^{12}\left(\sum_{i \in S}\left|E_{S}\right|\right) \geq 5 \sum_{S}\left|E_{S}\right|=5 n .
Therefore n≤48n \leq 48.

Now, define a sequence {ci}i=152\{c_{i}\}_{i=1}^{52} of colours in the following way:
123456789101112412385671291011341278561112910234167851011129 \begin{array}{llllllllllll} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 4 & 1 & 2 & 3 & 8 & 5 & 6 & 7 & 12 & 9 & 10 & 11 \\ 3 & 4 & 1 & 2 & 7 & 8 & 5 & 6 & 11 & 12 & 9 & 10 \\ 2 & 3 & 4 & 1 & 6 & 7 & 8 & 5 & 10 & 11 & 12 & 9 \\ \end{array}
The first row lists c1,…,c12c_{1}, \ldots, c_{12} in order, the second row lists c13,…,c24c_{13}, \ldots, c_{24} in order, the third row lists c25,…,c36c_{25}, \ldots, c_{36} in order, and finally the last row lists c37,…,c48c_{37}, \ldots, c_{48} in order. For each j,1≤j≤48j, 1 \leq j \leq 48, assign colours cj,cj+1,cj+2,cj+3,cj+4c_{j}, c_{j+1}, c_{j+2}, c_{j+3}, c_{j+4} to the jj-th clown. It is easy to check that this assignment satisfies all conditions given above. So, 48 is the largest for nn.

Remark: The fact that n≤48n \leq 48 can be obtained in a much simpler observation that
5n≤12×20=240. 5 n \leq 12 \times 20=240 .

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

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