Maths Olympiad Prep

Library / /20 of 21

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 SSS \neq S^{\prime} implies ESES=E_{S} \cap E_{S^{\prime}}=\emptyset, we have
SES=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,
ESEi if and only if iS, E_{S} \subseteq E_{i} \quad \text{ if and only if } \quad i \in S,
and hence
Ei=iSES. \left|E_{i}\right|=\sum_{i \in S}\left|E_{S}\right| .
By assumption, we know that Ei20\left|E_{i}\right| \leq 20 and that if ESE_{S} \neq \emptyset, then S5|S| \geq 5. From this we obtain
20×12i=112Ei=i=112(iSES)5SES=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 n48n \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,1j48j, 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 n48n \leq 48 can be obtained in a much simpler observation that
5n12×20=240. 5 n \leq 12 \times 20=240 .

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 and solution reproduced as published; topic and difficulty added by this site.