第3問

平面上に、どの3点も一直線上にない2004点の集合 S があり、S の2点で定まるすべての直線の集合を L とする。直線が2点を分離するとは、2点がその直線の反対側にあり、どちらも直線上にないこととする。S を高々2色で彩色し、2点が同色であることと、それらを分離する L の直線の本数が奇数であることが同値となるようにできることを証明せよ。

ステップ 1/5: 分離の偶奇性を定義する

前のステップ次のステップ

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

詳しい解説

2点 x,y に対し、n(x,y) をそれらを分離する L の直線本数とし、2を法として考える。S の点 p を選び p を青とし、n(p,q) が奇数なら q を青、偶数なら赤とする。