MathLabs

Problem 5

In a circus, nn clowns dress and paint themselves using a selection of 12 distinct colours. Each clown must use at least five different colours. The ringmaster requires that no two clowns have exactly the same set of colours and that no more than 20 clowns use any one particular colour. Find the largest possible nn.
Step 2 of 6: Double-count colour incidences
Previous stepNext step
∑i=112∣Ei∣=∑S⊆{1,…,12}∣ES∣ ∣S∣≥5n\sum_{i=1}^{12}|E_i|=\sum_{S\subseteq\{1,\ldots,12\}}|E_S|\,|S|\ge5n
Detailed analysis

Let ESE_S be the set of clowns whose colour set is exactly SS. The sets ESE_S partition the nn clowns. Each nonempty ESE_S has ∣S∣≥5|S|\ge5, hence ∑i=112∣Ei∣=∑S∣ES∣ ∣S∣≥5∑S∣ES∣=5n\sum_{i=1}^{12}|E_i|=\sum_S|E_S|\,|S|\ge5\sum_S|E_S|=5n.