【附】纯文本如下：
一道图论背景难题（2017集训队）的简单解法
冯跃峰
2017年中国国家集训队第3轮测试中有如下一个图论背景的组合问题：
【题目】将2017×2017方格棋盘的每个方格染黑白2色之一，使每个方格至少与一个同色方格相邻（有公共边）。黑、白方格的集合分别记为V1、V2，对Vi（i=1，2）中每两个相邻的方格的中心都用一条线段连接，得到的图记为Gi。试证：如果G1、G2都是连续的折现（无环路，不分岔），则棋盘的中心必定是G1或G2的端点。
【述评】本题应该算是一道“难题”，因为当年参加集训的学生中除9人得分外，其余考生都得0分。原解答也很繁，占用了近2个版面的篇幅（见《走向IMO（2017）》p123）。我们这里给出一个简单的证明，只需12行字就够了。从这个角度看，本题似乎又不算“难题”。
有趣的是，我们的解答中几乎只用到小学的知识，这是本题的一大特色，也是组合问题的魅力所在。
【题感】从条件看，似乎有图论背景，但又不是纯碎的图论问题，因为涉及到格的位置，比如“中心”。
不过，借用图论的语言，条件可简单地表述为：Gi（i=1，2）都是无圈的连通图，且每点的度大于0小于3。
由于“边”不仅隐含格的相邻性，还包含了方向与位置，自然想到研究图的局部性质：由一条边的方向研究下一条边的方向，由此不断扩展，期望找到折线的端点。
那么，先取哪个局部呢，这当然依赖于解题目标。
从目标看，证明折线有一个端点为“中心格”，不妨先考察两折线以“中心格”为一个端点时，折线的整体结构，借以发现“端点”的可能分布。
容易发现合乎条件的两条折线如下：
图1
由图可知，有两个端点在角上，由此想到从角格出发，不断扩展，直至找到两折线4个端点的位置——位于两对角线上。
进而只需证明：有一个端点同时位于两对角线上（中心）。
【局部性质】考察格a11，若它不是端点，则它的度为2，必定向右方和下方连边。同样，若格a22也不是端点，则必定向右方和下方连边（图2）。
【局部扩展】如此下去，必定可以找到i（1≤i<n=2017），使格a11，a22，…，ai-1，i-1都不是端点，而格aii是端点。其中i<n是显然的，否则ann是孤立点（图2），不连通，矛盾。
图2 图3
【平行推理】对称地，必定可以找到j（1<j≤2017），使格ann，an-1，n-1，…，aj+1，j+1都不是端点，而格ajj是端点。
如果i=j，分别考察格ai-1，i-1、ai+1，i+1引出的两条边组成的两个“直角”。 当两个直角同色时，aii是另一色的孤立点，矛盾；当两个直角异色时，aii必与其中一个直角同色，产生长为4的同色圈（图3），矛盾。
所以i≠j，这表明，135 º主对角线r1上至少两个端点（拟对象）。
下面只需说明两个“拟对象”（端点）中有一个端点同时在另一条对角线上，这类似考察另一条对角线即可。
【平行推理】同理，45 º主对角线r2上至少两个端点。
以下只需说明这两组端点中有两个重合（因为同一组的两个端点不重合），这从反面考虑即可。
【反面思考】如果4个端点互异，则2条折线的所有端点都在这两条对角线上。
如何产生矛盾？这显然要利用“折线”的特征：每条边连接的都是两个相邻格，从而每条折线都是奇格偶格交替的序列。它类似于国际象棋盘各格黑白相间，但方格已被红蓝染色，再黑白染色产生歧义，利用格的奇偶性比较方便，为此我们需要给出奇偶格的定义。
【引入定义】对于格aij，如果i+j为奇（偶）数，则称之为奇（偶）格。
【奇偶分析】显然任何相邻两个不同奇偶，两条对角线r1、r2上的格都为偶格。
由于黑折线两个端点都是偶格，且各格奇偶交替排列，从而黑折线上共有奇数个格。同理，白折线上共有奇数个格。由此可见，棋盘共有偶数个格。
但棋盘格的个数20172是奇数，矛盾。
【新写】考察a11，若它不是端点，则它必向右方和下方连边。接着考察a22，如此下去必定找到i（1≤i<n），使a11，a22，…，ai-1，i-1都不是端点，而格aii是端点。对称地，必定找到j（1<j≤n），使ann，an-1，n-1，…，aj+1，j+1都不是端点，而格ajj是端点（n=2017）。
若i=j，则ai-1，i-1、ai+1，i+1引出的两个“直角” 包围着格aii使其成为孤立点，或者一个直角与aii构成长为4的同色圈，矛盾。于是，135 º主对角线上至少两个端点。同理，45 º主对角线上至少两个端点。若中心格不是端点，则以上4个端点互异，包含了2条折线的所有端点。
对于格aij，若i+j为奇（偶）数，则称之为奇（偶）格。由上可知，黑折线两个端点都是偶格，且折线各格奇、偶交替排列，从而黑折线上共有奇数个格。同理，白折线上共有奇数个格。由此可见，棋盘共有偶数个格，与总格数20172是奇数矛盾。证毕。
联系客服
