第3题

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

第 5/5 步：得出染色性质

n(q,r)\equiv n(p,q)+n(p,r)+1\pmod2

详细分析

上一步的恒等式说明 n(p,q)+n(p,r)+n(q,r) 为奇数。因此 n(q,r) 为奇数当且仅当 n(p,q),n(p,r) 奇偶性相同,这正是 q,r 同色的条件。整个染色只使用蓝、红两色。