【附】纯文本如下:
一道图论背景难题(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是奇数矛盾。证毕。
联系客服