马步循环(批注版).doc

“马步循环” 新问题华南师大附中高三（2）班 顾家齐指导老师 罗碎海中国象棋与国际象棋之间有许多重大差异，前者的棋子放在纵横直线的交叉点上，而后者的棋子却放在格子内部。大家知道，中国的象棋的“马”是走“日”字（直立或卧倒的“日”字都行），蹩脚马就不能走动。国际象棋里也有“马”，也是斜着走：横两格直一格或横一格直两格，但无“扎马脚”的限制，所以行动更灵活。 123456国际象棋里的“马”可以从棋盘上的任何一格出发，不重不漏地走遍整个棋盘上的每一个格子，最后回到原先的出发点，这就是所谓的“马步循环”问题，在数学历史上被欧拉等数学家圆满解决。今天我们探讨一个新问题：图一1、问题：现有一个66的国际象棋棋盘（图一），一只马能否六步（包括把马放到棋盘上的一步）内把棋盘的所有行和列都走遍？答案：不可能。图二证明：我们从最后两步开始思考。假设存在满足要求的走法，则前四步走过了4行、4列，只剩两行两列未走过，而这未走的两行两列交汇形成了一个2*2的可行范围。由于这个22的范围内还有一步可走，所以这个范围必为图二的形式。（其中非阴影区域为可行范围，阴影区域为不可行范围，下同）。不妨设这个范围是横着放在图一的棋盘上的，占据A、B、C、D、E、F中连续的三列，占据1、2、3、4、5、6中相邻的两行。若这个范围占据2与3两行或3与4两行或4与5两行，那么前四步中必定会出现马一步迈过三行或以上（以2与3为例，前四步走过了1、4、5、6四行，其中必有一步是从第1行迈向4、5、6三列或从4、5、6三列迈向第1列的），这违反了马走“日”字的规定。因此这个范围只能占据1与2或5与6。由对称性，不妨设这个范围占据5与6两行。同时，这个范围可能占据ABC或BCD或CDE或DEF，由于图形对称性，只研究CDE和DEF两种情况。 图四图三若为DEF，则前四步只走过A、B、C、E四列，1、2、3、4四行。若第二步或第三步落在E列，则上一步与下一步都落在C列，无法在六步内走过全部六列（抽屉原理）。因此马只能在第一步或第四步落在E列。不妨设其第一步落在E列，则第二步落在C列。这其中共有六种情况：E1目测图四要旋转90C2，E2C1，E2C3，E3C4，E3C2，E4C3。这六种情况后的第三、四步的可行范围如图三、图四。其中图三对应E1C2，E2C1，E3C4，E4C3四种情况，图四对应E2C3，E3C2两种情况。显然，无法完成第三、四步。若第四步落于E列，同理可得亦不可行。若为CDE，同理F列必为第一步或第四步的落点，亦不可行。综上，不存在满足要求的走法。2、问题推广将问题推向任意正整数n，满足要求的走法是否存在呢？（为第一步，为第二步，依次类推）4*4的情况漏一种 A B C D1 2 3 4 对于4*4格子，由对称性知起点位置有三种A1，B1，B2再由对称性合并了一些情况只有第2种和第4种是可以循环的（3）33，存在（2）22，不存在（1）11，当然存在（4）44，存在（3种） （5）55，存在（8）88，存在（6）66，不存在，已证（7）77，存在3、一般结论（1）猜想：n=4k、4k+1、4k+3时存在满足要求的走法，n=4k+2时不存在满足要求的走法。但为什么是这样呢？4可能是一个周期。回过头去看看44的第二种走法与88的走法，可以发现44是一个可以无限循环的走法（我们不妨称它为循环节）。所以只需要k次重复，任何4k4k的棋盘都有满足要求的走法。因此n=4k时必存在满足要求的走法。n=4k+1与4k+3呢？其实，我们可以把它们分开为三部分4k部分，1部分，3部分。 1部分 3部分4k部分A端第4k-3步第4k-1步第4k-2步第4k步3部分 4k部分（A端）4k部分（B端）第4k-3步第4k-1步第4k-2步第4k步第4k+1步 1部分其中1部分能接在4k部分的B端（如上图），3部分能接在4k部分的A端（如下图）因此，n=4k+1与4k+3时，都存在满足要求的走法。下面证明n=4k+2时不存在满足要求的走法。要证明这个命题，需先证明下面三个命题：（1） n=2时不存在满足要求的走法；（2） 不存在nn（n不是4的倍数）的循环节；（3） 不存在不需要循环节（尤其是44）的走法。命题（1）显然成立。现证明命题（2）：（下面的论证中，（a，b）代表第a行第b列）先看看循环节的特点。对一个n*n循环节而言，其第一步必为（1,1），最后一步必为（n，n-1）或（n-1，n）（因为第n+1，即下一个循环的第一步要位于下一循环的（1,1）处）。易得n=1,2,3时不为循环节，n=4时为循环节。 列行1234512345若n=5，我们不妨以引入国际象棋中的黑白格。第一步（1,1）黑格第二步（2,3）或（3,2）白格第三步黑格 第四步白格第五步黑格而（5,4）与（4,5）皆为白格，第五步不能到达，所以5*5不会是循环节。若n=6，则更不可能是循环节。若n6，则n-15。我们取前五行和前五列讨论。分析不够严谨对于第1步有两种情况（1,1)和（1,2）（2,1）因为从上一个循环节跳进来可以有这三个落点。第二种情况也是上面漏掉的。分析过程相似第一步（1,1）第二步（2,3）或（3,2）。以（3,2）为例。第三步（2,4）或（4，4）或（5,3）若第三步为（2,4），则第四步为（4,3）或（4,5）。若第四步为（4,3）则形成了44循环节，最后必会形成对11或22或33循环节的论证，显然不存在nn循环节。 列行1234512345若第四步为（4,5），则此后必定有一步要从第3列跃到第6、7列或是反过来，不符合马走“日”字的规则，不成立，舍去。若第三步为（4,4），则此后必定有一步要从第2行跃到第5、6行或是反过来，不符合马走“日”字的规则，不成立，舍去。若第三步为（5,3），易得循环节中最后的一步必将落入第二行，与循环节的最后一步必落到（n，n-1）或（n-1，n）矛盾，舍去。所以第二步不为（3,2）。同理可得第二步不为（2,3）。综上，不存在nn（n不是4的倍数）循环节。证明命题（3）。首先说明，这里我们所说的走法不需要循环节（只有44循环节，如右图），是指这个走法中不存在连续的四步走过连续四行和四列的情况。如此前55的走法中，虽然其中没有我们所知道的44循环节，但事实上，其中的步是走过了25行与25列，是可以用4*4循环节取而代之的，因此我们说这个走法还是需要44循环节的。假设存在不需要44循环节的走法。第一步 第二步 第三步（1,1）（3,2）（2,4）或（4,4）或 （2,3）（证明过程同（3,2） （5,3）因为n9的情况我们都已经列举，而这些走法都是需要44循环节的（n4时只需要1部分与3部分），所以我们从n=9开始。只需证（1,1）（3，2）这种情况。用与命题（2）相同的证法可得，（1,1）（3,2）（2,4）与（1,1）（3,2）（2,4）这两种走法都不可行。因此，只有（1,1）（3,2）（5,3）这种不需要循环节的走法需要证明不存在性。有一处笔误应该是（4,4）前两种走法不可行为什么由（2）的证明可以知道？（2）的证明是在循环节走法的约束下的。反正我没弄懂若有这种走法，对于nn的棋盘而言，第n步必定落于第二行，第n-1步必定落于第四行。列行n-2n-1n12第n步3456用黑白格的方法。第一步（1,1）为黑格，若n为奇数，则第n步也落于黑格，而因为（2，n）为白格，第n步只能落于（2，n-1）；若n为偶数，则第n步落于白格，而因为（2，n）为黑格，第n步只能落于（2，n-1）。 那么对第n-1步而言，可行范围如右图（其中非阴影区域为可行范围，阴影区域为