第3题

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

第 3/5 步：去掉不经过三角形顶点的直线

n(p,q)+n(p,r)+n(q,r)\equiv n_1+\cdots+n_7\pmod 2

详细分析

画出三角形 pqr 及其七个区域。L 中不经过 p,q,r 的任一直线与三角形边交于偶数个点,所以对三个分隔数之和的贡献为偶数。因此只需考察经过三个顶点之一及七个区域中一点的直线。