第5题

平面上有 2n+1 个点，任意三点不共线且任意四点不共圆。若一个圆经过其中 3 个点且内部恰有 n-1 个点，则称其分割该点集。证明分割点集的圆的数目为偶数当且仅当 n 为偶数。

第 2/5 步：跟踪内部点数的变化

X_i\in R\Longleftrightarrow X_i\text{ lies inside }C_j\ (i<j),\quad X_j\in L\Longleftrightarrow X_j\text{ lies inside }C_i

详细分析

当 i<j 时，Ci 包含 Cj 在 R 侧的点，而 Cj 包含 Ci 在 L 侧的点。因此若 fi 是 Ci 内部点数，则 Xi、Xi+1 在异侧时 fi+1=fi；二者都在 L 时 fi+1=fi-1；二者都在 R 时 fi+1=fi+1。