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) 集合。真包含关系无自反性且具有传递性，两个圆盘不可能互相真包含。