送交者: lyz 于 September 06, 2001 15:07:13:
回答: 染格定理 由 老椰子 于 September 06, 2001 13:14:03:
［证明］任取一种染法。
如果有二竖列每列各有三格以上同色则定理为真。舍此则是：没有二竖列每列各有
三格以上同色。
对任一竖列，任三格不同色（二染二未染）有六种可能（C［２，４］＝６）。如果
有两个如此的竖列则定理为真。舍此则是：七列中必有一列三格以上同色。不妨假
设第一列下三格已染，考虑去掉第一行和第一列的这个矩形的子矩形（横六竖三）。
如果某个竖列有两格已染则定理为真（第一列下三格已染）。舍此则是：此六列只
能取一格未染和只染一个的四种形式（1＋C［１，３］＝４）。这样，至少有两列
形式相同，于是定理为真。
总之，定理恒为真。
对竖列的个数为六情形，如下染法就是个反例：
（１，１）（１，２）（１，３）
（２，３）（２，４）（２，５）
（３，２）（３，５）（３，６）
（４，１）（４，４）（４，６）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
C［m，n］：从n个元素中取m个元素的组合。