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。因此答案为肯定。