MathLabs

第6問

平面上の有限個の点が与えられ、各点は整数座標をもつ。座標軸のいずれかに平行な任意の直線 LL 上で、その直線 LL 上の白点数と赤点数の差の絶対値が高々 11 となるように、常に点を赤または白に塗り分けられるか。
ステップ 4/4: 点集合に戻る
ざっくり言うと

グラフの議論は各連結成分に局所的に適用でき、要求された直線条件は頂点での差の上限と同じである。

∣#white(L)−#red(L)∣≤1|\#\text{white}(L)-\#\text{red}(L)|\le1
詳しい解説

各連結成分を独立に彩色する。辺の色を点の色に戻せば、任意の水平・垂直線 LL について ∣#white(L)−#red(L)∣≤1|\#\text{white}(L)-\#\text{red}(L)|\le1 となる。よって答えは肯定である。