设 $n$ 为任意给定的正整数，$T$ 是平面上所有满足 $x+y<n,x,y$ 为非负整数的点 $(x,y)$ 所组成的集合．$T$ 中每一点 $(x,y)$ 均被染上红色或蓝色，满足：若 $(x,y)$ 是红色，则 $T$ 中所有满足 $x^\prime \leqslant x,y^\prime \leqslant y$ 的点 $(x^\prime,y^\prime)$ 均为红色．如果 $n$ 个蓝点 的横坐标各不相同，那么称这 $n$ 个蓝点所组成的集合为一个 $X-$ 集；如果 $n$ 个蓝点 的纵坐标各不相同，那么称这 $n$ 个蓝点所组成的集合为一个 $Y-$ 集．求证：$X-$ 集的个数和 $Y-$ 集的个数一样多．（哥伦比亚）
【难度】
【出处】
2002年第43届IMO试题
【标注】
【答案】
略
【解析】
设红点个数为 $m$，$X-$ 集合数目为 $t$，$Y-$ 集合数目为 $s$，对 $m,0\leqslant m\leqslant \dfrac{n(n+1)}{2}$，进行归纳证明．
当 $m=0$ 时，由乘法原理，$s=t=n!$，命题成立．
假设 $m=k\left(0\leqslant k\leqslant \dfrac{n(n+1)}{2}\right)$ 时命题成立．
对于 $m=k+1$，设点 $P(x_0,y_0)$ 是使 $x_0+y_0$ 最大的红点之一，那么将 $P$ 改为蓝点．由于不存在其他红点 $(x,y),x\geqslant x_0,y\geqslant y_0$，因此，这仍然是一个满足条件的集合，记为 $T^\prime$．对它类似地定义 $t^\prime,s^\prime$．
对于 $T^\prime$，设它在 $x=i(0\leqslant i\leqslant n-1)$ 列上的蓝点有 $a_i$ 个，在 $y=j(0\leqslant j\leqslant n-1)$ 行上的蓝点有 $b_j$ 个．那么 $\displaystyle t^\prime=\prod\limits_{i=0}^{n-1}a_i,s^\prime=\prod_{j=0}^{n-1}b_j$．由归纳假设有 $t^\prime =s^\prime $，即 $\displaystyle \prod\limits_{i=0}^{n-1}a_i=\prod_{j=0}^{n-1}b_j$．
对于改变前的集合 $T$，有 $\displaystyle t=\left(\prod\limits_{i=0,i\ne x_0}^{n-1}a_i\right)(a_{x_0}-1),s=\left(\prod\limits_{j=0,j\ne y_0}^{n-1}b_j\right)(b_{y_0}-1)$．
在 $x=x_0$ 列上，纵坐标大于等于 $y_0$ 的 $T$ 中的点有 $n-x_0-y_0$ 个，所以 $a_{x_0}=n-x_0-y_0$，同理 $b_{y_0}=n-x_0-y_0$，故 $a_{x_0}=b_{y_0}$．于是 $\displaystyle \left(\prod\limits_{i=0,i\ne x_0}^{n-1}a_i\right)(a_{x_0}-1)=\left(\prod\limits_{j=0,j\ne y_0}^{n-1}b_j\right)(b_{y_0}-1)$
即 $t=s$．故对 $m=k+1$ 时，命题成立．
因此，对一切 $0\leqslant m\leqslant\dfrac{n(n+1)}{2}$，命题成立．
当 $m=0$ 时，由乘法原理，$s=t=n!$，命题成立．
假设 $m=k\left(0\leqslant k\leqslant \dfrac{n(n+1)}{2}\right)$ 时命题成立．
对于 $m=k+1$，设点 $P(x_0,y_0)$ 是使 $x_0+y_0$ 最大的红点之一，那么将 $P$ 改为蓝点．由于不存在其他红点 $(x,y),x\geqslant x_0,y\geqslant y_0$，因此，这仍然是一个满足条件的集合，记为 $T^\prime$．对它类似地定义 $t^\prime,s^\prime$．
对于 $T^\prime$，设它在 $x=i(0\leqslant i\leqslant n-1)$ 列上的蓝点有 $a_i$ 个，在 $y=j(0\leqslant j\leqslant n-1)$ 行上的蓝点有 $b_j$ 个．那么 $\displaystyle t^\prime=\prod\limits_{i=0}^{n-1}a_i,s^\prime=\prod_{j=0}^{n-1}b_j$．由归纳假设有 $t^\prime =s^\prime $，即 $\displaystyle \prod\limits_{i=0}^{n-1}a_i=\prod_{j=0}^{n-1}b_j$．
对于改变前的集合 $T$，有 $\displaystyle t=\left(\prod\limits_{i=0,i\ne x_0}^{n-1}a_i\right)(a_{x_0}-1),s=\left(\prod\limits_{j=0,j\ne y_0}^{n-1}b_j\right)(b_{y_0}-1)$．
在 $x=x_0$ 列上，纵坐标大于等于 $y_0$ 的 $T$ 中的点有 $n-x_0-y_0$ 个，所以 $a_{x_0}=n-x_0-y_0$，同理 $b_{y_0}=n-x_0-y_0$，故 $a_{x_0}=b_{y_0}$．于是 $\displaystyle \left(\prod\limits_{i=0,i\ne x_0}^{n-1}a_i\right)(a_{x_0}-1)=\left(\prod\limits_{j=0,j\ne y_0}^{n-1}b_j\right)(b_{y_0}-1)$
即 $t=s$．故对 $m=k+1$ 时，命题成立．
因此，对一切 $0\leqslant m\leqslant\dfrac{n(n+1)}{2}$，命题成立．
答案
解析
备注
