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) 数目。求可能的最大得分。
第 2/6 步：记录被禁止的相邻有序对
上一步下一步
(i+1,i)∉SC (1≤i<n),(1,n)∉SC(i+1,i)\notin S_C\ (1\le i<n),\qquad(1,n)\notin S_C
详细分析

因为 CiC_i 的圆心在 Ci+1C_{i+1} 的圆周上，Ci+1C_{i+1} 不可能真包含 CiC_i。同理 CnC_n 的圆心在 C1C_1 上，所以 (1,n)∉SC(1,n)\notin S_C。这些就是被禁止的相邻对。