平面上有限个点构成一个集合，其中每个点的坐标都是整数．能否把此集合中的某些点染成红色而其余的点染成白色，使得与纵，横坐标轴平行的任一条直线上所含的红点的个数与白点的个数至多相差一个？证明你的结论．（民主德国）
【难度】
【出处】
1986年第27届IMO试题
【标注】
【答案】
略
【解析】
答案是肯定的．对平面上的已知点个数 $n$ 进行归纳．
$n=1$ 时，任意染色都满足要求．
假设点数 $<n$ 时，有符合要求的染色方法．下证当点数为 $n$ 时，也有符合要求的染色方法．为了方便，把与纵，横坐标轴平行的直线分别简称为纵线，横线．易知，对于符合要求的染色方法，纵线或横线上若有偶数个已知点，则红点的个数与白点的个数相等，若有奇数个已知点，则红点的个数与白点的个数恰好相差 $1$ 个．
（1）若至少有一条纵线或横线 $l$ 上有奇数个点，把其中的一点 $P$ 去掉，这时 $l$ 上只有偶数个点（也可能没有已知点），连通其他的点共 $n-1$ 个，由归纳假设，有符合要求的染色方法．再考虑点 $P$，由于 $l$ 上除 $P$ 外是偶数个点，所以红点与白点各占一半，如果 $P$ 还在另一条直线（纵线或横线）$l^\prime$ 上，当 $l^\prime$ 上红点与白点一样多时，$P$ 可以任意染色，当 $l^\prime$ 上红（或白）点比白（或红）点多 $1$ 个时，$P$ 就染成白（或红色），这样，所有 $n$ 个点都染成符合题意的颜色了．
（2）若所有得到的纵线和横线上都含有偶数个已知点．先把一条纵线 $m$ 上的偶数个点去掉，对剩下的点用归纳假设，可以把它们都染成符合题意的颜色，并且这时各纵线上的红点和白点一样多．而横线有两种情形：一种是不含 $m$ 上的点，这种横线上的红点和白点一样多；另一种是含 $m$ 上的一个点，这种横线上已染色的点数是奇数，所以红点比白点多一个或白点比红点多一个，并且红点多的横线条数与白点多的横线条数相等（这是因为所有已染色的红，白点数相等）．于是，在红点多的横线上，$m$ 中的点染白色，白点多的横线上，$m$ 中的点染红色，这样，$m$ 上的红点和白点个数一样多，这时，所有 $n$ 个点都染成符合题意的颜色．
综上所述，命题得证．
$n=1$ 时，任意染色都满足要求．
假设点数 $<n$ 时，有符合要求的染色方法．下证当点数为 $n$ 时，也有符合要求的染色方法．为了方便，把与纵，横坐标轴平行的直线分别简称为纵线，横线．易知，对于符合要求的染色方法，纵线或横线上若有偶数个已知点，则红点的个数与白点的个数相等，若有奇数个已知点，则红点的个数与白点的个数恰好相差 $1$ 个．
（1）若至少有一条纵线或横线 $l$ 上有奇数个点，把其中的一点 $P$ 去掉，这时 $l$ 上只有偶数个点（也可能没有已知点），连通其他的点共 $n-1$ 个，由归纳假设，有符合要求的染色方法．再考虑点 $P$，由于 $l$ 上除 $P$ 外是偶数个点，所以红点与白点各占一半，如果 $P$ 还在另一条直线（纵线或横线）$l^\prime$ 上，当 $l^\prime$ 上红点与白点一样多时，$P$ 可以任意染色，当 $l^\prime$ 上红（或白）点比白（或红）点多 $1$ 个时，$P$ 就染成白（或红色），这样，所有 $n$ 个点都染成符合题意的颜色了．
（2）若所有得到的纵线和横线上都含有偶数个已知点．先把一条纵线 $m$ 上的偶数个点去掉，对剩下的点用归纳假设，可以把它们都染成符合题意的颜色，并且这时各纵线上的红点和白点一样多．而横线有两种情形：一种是不含 $m$ 上的点，这种横线上的红点和白点一样多；另一种是含 $m$ 上的一个点，这种横线上已染色的点数是奇数，所以红点比白点多一个或白点比红点多一个，并且红点多的横线条数与白点多的横线条数相等（这是因为所有已染色的红，白点数相等）．于是，在红点多的横线上，$m$ 中的点染白色，白点多的横线上，$m$ 中的点染红色，这样，$m$ 上的红点和白点个数一样多，这时，所有 $n$ 个点都染成符合题意的颜色．
综上所述，命题得证．
答案
解析
备注
