MathLabs

第5問

サーカスに nn 人の道化師がおり、12色の異なる色から選んで服装と化粧をする。各道化師は少なくとも5色を使う。団長は、同じ色の集合を使う道化師が2人おらず、どの1色も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。