第5题

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

第 4/5 步：计数所有点对

\sum_{\{A,B\}}q_{AB}=3G,\qquad \binom{2n+1}{2}=n(2n+1)\equiv n\pmod2

详细分析

设 qAB 为经过 A、B 的分割圆数，G 为分割圆总数。根据上一步每个 qAB 都是奇数。对所有点对求和得到 3G，因为每个分割圆恰有三个点对。点对共有 binomial(2n+1,2)=n(2n+1) 个，其奇偶性为 n。因 3 为奇数，G 的奇偶性为 n。