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) の個数を得点とする。得点の最大値を求めよ。
ステップ 6/6: 構成を与える
前のステップ次のステップ
max⁡score⁡=(n−1)(n−2)2\max\operatorname{score}=\frac{(n-1)(n-2)}2
詳しい解説

達成のため、C2C_2 を C1C_1 内に、C3C_3 を C2C_2 内に順に置き、Cn−1C_{n-1} まで各前円板の中心が次の円周上に来るようにする。CnC_n は中心を C1C_1 の円周上、円周を Cn−1C_{n-1} の中心を通るように選ぶ。このとき包含はちょうど 1≤i<j≤n−11\le i<j\le n-1 であり、(n−1)(n−2)2\frac{(n-1)(n-2)}2 を得る。