Browse · MathNet
PrintAsia Pacific Mathematics Olympiad (APMO)
counting and probability
Problem
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.
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
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
Final answer
48
Techniques
Counting two waysColoring schemes, extremal arguments