2014 IMO Problem 2 Solution （兼谈本题与麻将之间的某些关联）

下面是我对2014 IMO 的第二题的解答， 采用的是很常见的思路：1。先用抽屉原则（Pigeonhole Principle）定出f（n）的下界； 2。再用构造法定出f（n）的上界； 3。最后证出f（n）的单调性从而把上面的上下两个界合二为一。 整条思维线路清晰而且自然，犹如行云流水，一气呵成，这是解决这类IMO组合题的典型的教科书式的方法（textbook method）。但是要一步一步地写清楚让别人看明白，真是费劲啊！对不起，让大家等了一个星期才用空写出严格的详细证明。

最后说些题外话， 解这道题时让我想起了数学和麻将之间的某些关联，一周前的周六（7/12）晚上，当我用构造法定出f（n）的上界的时候， 我是先考虑一些特例（如n=9）， 见我的证明第三页中的图3，当n=3X3=9时原题演变为如何把9个车（rook）“尽最大可能分散”放在9行9列的棋盘上， 我立刻想到了麻将中“十三不靠"打法的口诀：一四七，二五八，三六九， 于是我把前3列的3个车放在一四七的位置，中间3列的3个车放在二五八的位置，最后3列的3个车放在三六九的位置， （见图3），这样9行9列的棋盘上就没有3X3 的空盘了，有此可得f（9）<=2, 进而同样的原理很容易推广到k行k列一般的棋盘上。 哈哈，我们老祖宗的麻将国粹真英明，这道题的构造部分真是轻松，得来全不费功夫！

把这些我解IMO题时的花絮写出来， 与大家分享， 是想告诉大家，IMO题并非都像大家想象的那样可怕和枯燥无味， 其实不少IMO题都是积各类解题技巧和人类智慧中的精华于一身的好题， 也许您平常生活中的一个小窍门，也许您玩麻将时的一个“十三不靠"的小常识， 这些都会成为IMO 赛场上成功的一把一把的小钥匙。 如果您还是不信的话， 我再告诉您2014 IMO 第五题我给出的解答中运用的greedy algorithm 就是您平常生活中的一个小窍门： 假如现在有一些很大的石头，一些一般大的石头， 一些小石头， 和一大堆细沙子，您要把上述石头和沙子放入一个容积与这些石头和沙子相同的缸中， 请问应该如何放？平常生活中的常识告诉我们应该先放大石头，然后放一般的石头和小石头， 最后放细沙子， 这与2014 IMO 第五题的解法有着异曲同工之妙，（2014 IMO 第五题问如何把一堆面值为1/n （n= 2， 3， 。。。）的硬币分组使得每组的硬币价值之和不超过1，） 这种“先放石头，后放沙子”的做法几乎是所有greedy algorithm的最重要的基石。

数学来源于生活，不少IMO的题目也是这样!

希望明年的IMO再来几道像这样的积各类解题技巧和人类智慧中的精华于一身的好题， 明年再见， 2015 IMO！
 

所有跟帖： 

• 你自己高中的时候喜欢自己琢磨数学题吗？ -夏小草- ♀ (0 bytes) () 07/20/2014 postreply 14:46:03

• 先赞一下！解答等到自己琢磨一下以后再看。 -ca981- ♂ (0 bytes) () 07/20/2014 postreply 15:55:46

• 谢谢分享！ -CarriePanda- ♀ (0 bytes) () 07/20/2014 postreply 20:48:33

• 我也想了一种思路，不知道是否正确 -ca981- ♂ (302 bytes) () 07/21/2014 postreply 07:28:13

• 疏忽了，排成一排不符合基本要求要求。 -ca981- ♂ (0 bytes) () 07/21/2014 postreply 10:01:09

• 对于n=k^2+1，有一个完美的鸽巢原理的应用 -ca981- ♂ (118 bytes) () 07/21/2014 postreply 19:10:55

• 忘了考虑那个“车”正好在顶角上。如果正好在某个顶角上，那就避开这个顶角，选另一个边界。 四个顶点最多同时只有两个对角“车” -ca981- ♂ (0 bytes) () 07/21/2014 postreply 19:17:56

• 解释得很好很清楚，谢谢 -6700417- ♂ (0 bytes) () 07/25/2014 postreply 18:06:05

• 我在群组里贴了第 2 题的一种解法 -ca981- ♂ (343 bytes) () 07/27/2014 postreply 09:52:21

• 谢谢 -怪哉- ♂ (18 bytes) () 07/21/2014 postreply 09:01:27