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。