MathLabs

第5题

平面上有 2n+1 个点,任意三点不共线且任意四点不共圆。若一个圆经过其中 3 个点且内部恰有 n-1 个点,则称其分割该点集。证明分割点集的圆的数目为偶数当且仅当 n 为偶数。
第 3/5 步:证明分割圆数为奇数
#{i:fi=n−1}≡1(mod2)\#\{i:f_i=n-1\}\equiv1\pmod2
详细分析

Ci 分割点集当且仅当 fi=n-1。沿排序序列移动时,跨过水平 n-1 只有在进入或离开该水平时,位于该水平上的指标数奇偶性才改变。若有一段连续指标都在该水平上,则两端 Xi 的半平面标签必须交替,因此该段长度为奇数。比较首尾圆(若端点恰在该水平上,则用同样的单侧论证)可知,从奇偶意义看序列首尾在相反侧。因此满足 fi=n-1 的指标数为奇数。于是对任意 A、B,经过它们的分割圆数为奇数。