MathLabs

第3問

平面上に、どの3点も一直線上にない2004点の集合 S があり、S の2点で定まるすべての直線の集合を L とする。直線が2点を分離するとは、2点がその直線の反対側にあり、どちらも直線上にないこととする。S を高々2色で彩色し、2点が同色であることと、それらを分離する L の直線の本数が奇数であることが同値となるようにできることを証明せよ。
ステップ 3/5: 三角形の頂点を通らない直線を除く
n(p,q)+n(p,r)+n(q,r)≡n1+⋯+n7(mod2)n(p,q)+n(p,r)+n(q,r)\equiv n_1+\cdots+n_7\pmod 2
詳しい解説

三角形 pqr とその7領域を描く。p,q,r のいずれも通らない L の直線は三角形の辺を偶数回横切るため、3つの分離数への寄与は偶数である。したがって、3頂点のいずれかと7領域の点を結ぶ直線だけを考えればよい。