MathLabs

第3問

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

前段の恒等式から n(p,q)+n(p,r)+n(q,r) は奇数である。したがって n(q,r) が奇数であることは n(p,q),n(p,r) が同じ偶奇であることと同値であり、これは q,r が同色であることに等しい。彩色は青と赤の2色だけである。