抽屉原理（七）

做最好的数学教育公众号——从小学到研究生。 

来都来了，敬请关注“甬上煌言”，或者直接搜doubimather，逗逼数学人。

更加欢迎置顶。

今天我们来看几个难题。

毕竟新年要有新气象嘛。

将一个5×5的方格每个方格都染成黑、白两种颜色之一，求证：一定存在一个长方形，四个顶点处的四个方格同色。

每个格子可以选择黑白，一共有2的25次种不同的染色方式。我们只存在理论上的可能做到把所有情况都写出来（计算机当然可以），草稿纸也不便宜。

分章节的练习其实有个非常大的好处就是给了你大致的方向。比如这个染色问题，你就知道要用抽屉原理来做。

问题是：抽屉在哪里？还是这个老问题。

我们想四个顶点同色，肯定是要分组，然后保证两组装进同一个抽屉里。

根据抽屉原理，一般都是至少两个啥落进同一个抽屉里，对吧？

所以，四个顶点应该被分成两组，也就是说我们需要把原命题改为：求证，必然有两组同色的顶点能构成矩形。

问题又来了：这四个同色顶点怎么能构成矩形呢？

必然是除去连对角线以外，两两同行同列。

所以题目就变成了求证在一个5×5的矩形中，一定有除去连对角线以外的同行同列的四个点是同色的。

你可能要问了贼老师这有什么用啊？

这就是我一直强调的先要把题目变成数学语言啊。

然后再考虑，我先证明第一行一定有两个同色的点行不行？这是很显然的。因为一共五个点，所以至少有两个点同色，我们记为A1，A2，不妨设同为白色。

那么我现在把B1-E1,染白色，B2-E2染黑色，无论怎么样也构不成同色矩形，构造失败。

失败的原因在哪里？

因为只有两列，你能选择的余地太小了。

我们不妨扩大一点选择范围，很显然，第一行内，至少有三个格子可以染相同颜色，对吧？我们不妨设在A1，A2，A3三个格子内染了白色。

在其余四行对应的列里，我们在每行最多只能涂一个白色，如果有两个白色的格子，马上就和第一行中某两个白色格子构成了我们要的矩形了。

那么只有一个白色的格子，我们用X表示黑色，Y表示白色，那只有YXX,XYX,XXY,XXX这样四种。

如果有一行挑了XXX，那么其他三行不管怎么染，一定存在一个顶点全为黑色的矩形；

如果没有一行挑XXX，那么四行三种染色方式，必然有一种染色方式染了两次，仍然能出来一个黑色的矩形。

题目就做完了。

是不是分析地丝丝入扣？

这也是我做这个题目的整个思考过程。直接构造是件很困难的事情，所以我们要东试试西试试，试验不可怕，可怕的是试验没有方向。

我们再看：将一个4×19的方格表每个方格都染成黑、白、红三种颜色之一，请证明：一定存在一个长方形，四个顶点处的四个方格同色。

还是先看第一行，第一行有19列，染三种颜色，所以至少有一种颜色有7个格子同色，不妨记做A1-A7染了黑色，仿照前面的题目，那么后面三行相同的7列里最多只能有一个格子染黑色，其余6个格子染两种颜色那么一共有7×2^6=508种情况。

好吧，此路不通。

因为我们希望的是来三种情况，这样抽屉就刚刚好，然而现在的抽屉数的零头都比我们预期的多，所以一定错了。

此时就要考虑换条路走了。问题出在哪里？我们考虑了对行染色，所以出现了太多情况，那么改改，对列染色？每列四个格子，那么肯定有一种颜色染了两格，4个格子里挑两格染成同色，一共有六种情况，一共有三种颜色，所以共有18种情况。

现在告诉我，一共有多少列？19列！

所以必然有两列在位置相同的地方染了同色，证毕。

这对小学生来说已经是相当难的抽屉原理的问题了，如果看懂了，恭喜你，你已经具备了小学奥数高手的潜质了！

关注贼老师

好好学习

天天向上