MathLabs

第3問

平面上の nn 個の円板 C1,C2,…,CnC_1,C_2,\ldots,C_n を考え、各 1≤i<n1\le i<n で CiC_i の中心が Ci+1C_{i+1} の円周上にあり、CnC_n の中心が C1C_1 の円周上にあるとする。CiC_i が CjC_j を真に含む順序対 (i,j)(i,j) の個数を得点とする。得点の最大値を求めよ。
ステップ 1/6: 包含関係を順序対で表す
前のステップ次のステップ
score⁡(C)=∣SC∣,SC={(i,j):Ci properly contains Cj}\operatorname{score}(C)=|S_C|,\qquad S_C=\{(i,j):C_i\text{ properly contains }C_j\}
詳しい解説

SCS_C を CiC_i が CjC_j を真に含む順序対 (i,j)(i,j) の集合とする。真の包含は反射的でなく推移的であり、2つの円板が互いに真に含むことはない。