第3题

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

第 1/5 步：定义分隔的奇偶性

n(x,y)=\#\{\ell\in L:\ell\text{ separates }x\text{ and }y\}\pmod 2

详细分析

对两点 x,y,令 n(x,y) 为分隔它们的 L 中直线条数,并按模 2 计算。取 p 属于 S 并染成蓝色;当 n(p,q) 为奇数时将 q 染蓝,为偶数时染红。