In a circus, there are $n$ 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 $n$ of clowns so as to make the ringmaster's order possible.
Problem
Source: APMO 2006, Problem 5
Tags: combinatorics unsolved, combinatorics, ez, easy
al.M.V.
25.03.2006 03:55
trivial stuff...20*12/5=48...the example is trivial as well...(fix 4 at a time)
Valiowk
25.03.2006 17:59
Perhaps the most bizarre thing is that according to the official solution, the bound is worth 5 (!) marks, and the construction is worth 2.
WOOT2016er
01.11.2015 23:55
What is the construction for $48$ colors? What is the motivation for finding it?
MathD
02.11.2015 00:03
Complete solution (with construction) of this problem is published here on page 48. http://estoyanov.net/files/MATAMATIKA/aziatsko_tihookeanski_matholimpiadi.pdf But I would also like to know the motivation.
AlexLewandowski
21.01.2017 20:21
Simplest solution.... Let $a_1$,$a_2$,.....$a_n$ denote the $n$ clowns and let $c_1$,$c_2$,.....,$c_{12}$ denote the 12 colors. Set up the incidence matrix. An entry is 1 if the clown corresponding to a color uses that color, and 0 otherwise. Count the no. of ones in two different ways. If N is the no. of ones, then we get $5n\le N\le 240$. From this inequality, we find our desired answer to be $48$.
FISHMJ25
24.08.2018 00:13
Here is easy example take $6$ groups of $8$ clowns .Mark these groups from $1$ to $6$ .In first group all clowns have form $1,2,3,4,k$ where $k$ is one of other 8 not used ($5\cdots,12$ in this case) (k will be defined similarly for others ) .Every clown in $2$ has form $5,6,7,8,k$.Third has $9,10,11,12,k$.Fourth $1,2,5,9,k$ ; Fifth $3,6,7,10,k$ and last one $4,8,11,12,k$