MathLabs

第5题

马戏团有 nn 个小丑，从 12 种互不相同的颜色中选色来着装和化妆。每个小丑至少使用五种不同颜色。团长要求任意两个小丑使用的颜色集合不完全相同，且每一种颜色至多被 20 个小丑使用。求可能的 nn 的最大值。
第 2/6 步：双计数颜色关联
上一步下一步
∑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
详细分析

令 ESE_S 为颜色集合恰为 SS 的小丑集合。各 ESE_S 将 nn 个小丑分割。非空的 ESE_S 都有 ∣S∣≥5|S|\ge5，故 ∑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。