In a circus, there are 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 of clowns so as to make the ringmaster's order possible.
Asia Pacific Mathematics Olympiad (APMO) competition problems
Solution
Let be the set of clowns. Label the colours . For each , let denote the set of clowns who use colour . For each subset of , let be the set of clowns who use exactly those colours in . Since implies , we have
where runs over all subsets of . Now for each ,
and hence
By assumption, we know that and that if , then . From this we obtain
Therefore .
Now, define a sequence of colours in the following way:
The first row lists in order, the second row lists in order, the third row lists in order, and finally the last row lists in order. For each , assign colours to the -th clown. It is easy to check that this assignment satisfies all conditions given above. So, 48 is the largest for .
Remark: The fact that can be obtained in a much simpler observation that