第84届莫斯科奥林匹克9年级第2题

9.2.8×8方格表中的每个方格都被染为两种颜色之一.证明,可从该方格表中剪下两个没有公共方格的2×2正方形,它们的染色情况完全相同(旋转后相同的不算相同).

证明:反证法,假设不可以。

2×2染色共有16种情况,8×8中共可剪下16个2*2的正方形,假设这16个里不存在染色情况相同的。对黄色1部分进行分析,假设黄色1与剩下的14个正方形还是没染色相同的,那么黄色1必然与其相交的两正方形之一染色相同,那么与其相交的两个正方形中必然有一个是两列颜色情况相同。同理可得与2345相交的8个正方形中必然有4个是两列颜色情况相同。而两列颜色情况相同一共有2*2=4种情况。而与黄色部分相交的10个正方形中有5个正方形的两列颜色情况相同。所以这5个正方形中,必然有两个正方形染色情况相同,与假设矛盾。

所以可从该方格表中剪下两个没有公共方格的2×2正方形,它们的染色情况完全相同。

原文地址:https://www.cnblogs.com/lau1997/p/14943160.html