第3题

设平面上有一个含 2004 个点的集合 S,且任意三点不共线;令 L 为由 S 中点对确定的所有直线的集合。若两个点位于直线的两侧且均不在直线上,就称该直线分隔这两个点。证明可以至多用两种颜色给 S 染色,使得两点同色当且仅当分隔它们的 L 中直线条数为奇数。

第 2/5 步：归结为三个点的奇偶恒等式

n(p,q)+n(p,r)+n(q,r)\equiv 1\pmod 2

详细分析

按此染色,q 与 r 同色当且仅当 n(p,q)+n(p,r) 为偶数。因此只需证明对互异的 p,q,r,有 n(p,q)+n(p,r)+n(q,r) 为奇数。