MathLabs

第3問

平面上に、どの3点も一直線上にない2004点の集合 S があり、S の2点で定まるすべての直線の集合を L とする。直線が2点を分離するとは、2点がその直線の反対側にあり、どちらも直線上にないこととする。S を高々2色で彩色し、2点が同色であることと、それらを分離する L の直線の本数が奇数であることが同値となるようにできることを証明せよ。
ステップ 4/5: 7領域を数える
(n1+n4+n7)+(n2+n5+n7)+(n3+n6+n7)=∑i=17ni=2004−3=2001≡1(mod2)(n_1+n_4+n_7)+(n_2+n_5+n_7)+(n_3+n_6+n_7)=\sum_{i=1}^7n_i=2004-3=2001\equiv1\pmod2
詳しい解説

n_i を、p,q,r を除く S の点で領域 i にあるものの個数とする。標準的な7領域の番号付けでは、p を通って q,r を分離する直線は領域1,4,7に対応し、q と r についてはそれぞれ 2,5,7 と 3,6,7 である。和は p,q,r 以外の各点をちょうど1回数えるので 2001、奇数である。