马步循环(批注版).docVIP

“马步循环” 新问题 华南师大附中高三（2）班 顾家齐 指导老师 罗碎海 中国象棋与国际象棋之间有许多重大差异，前者的棋子放在纵横直线的交叉点上，而后者的棋子却放在格子内部。 大家知道，中国的象棋的“马”是走“日”字（直立或卧倒的“日”字都行），蹩脚马就不能走动。国际象棋里也有“马”，也是斜着走：横两格直一格或横一格直两格，但无“扎马脚”的限制，所以行动更灵活。 国际象棋里的“马”可以从棋盘上的任何一格出发，不重不漏地走遍整个棋盘上的每一个格子，最后回到原先的出发点，这就是所谓的“马步循环”问题，在数学历史上被欧拉等数学家圆满解决。今天我们探讨一个新问题： 1、问题：现有一个6×6的国际象棋棋盘（图一），一只马能否六步（包括把马放到棋盘上的一步）内把棋盘的所有行和列都走遍？ 答案：不可能。 证明：我们从最后两步开始思考。假设存在满足要求的走法，则前四步走过了4行、4列，只剩两行两列未走过，而这未走的两行两列交汇形成了一个2*2的可行范围。由于这个2×2的范围内还有一步可走，所以这个范围必为图二的形式。（其中非阴影区域为可行范围，阴影区域为不可行范围，下同）。不妨设这个范围是横着放在图一的棋盘上的，占据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→C2，E2→C1，E2→C3，E3→C4，E3→C2，E4→C3。这六种情况后的第三、四步的可行范围如图三、图四。 其中图三对应E1→C2，E2→C1，E3→C4，E4→C3四种情况，图四对应E2→C3，E3→C2两种情况。 显然，无法完成第三、四步。若第四步落于E列，同理可得亦不可行。 若为CDE，同理F列必为第一步或第四步的落点，亦不可行。 综上，不存在满足要求的走法。 2、问题推广 将问题推向任意正整数n，满足要求的走法是否存在呢？（为第一步为第二步依次类推 （6）6×6，不存在，已证 3、一般结论 （1）猜想：n=4k、4k+1、4k+3时存在满足要求的走法，n=4k+2时不存在满足要求的走法。但为什么是这样呢？4可能是一个周期。 回过头去看看4×4的第二种走法与8×8的走法，可以发现4×4是一个可以无限循环的走法（我们不妨称它为循环节）。所以只需要k次重复，任何4k×4k的棋盘都有满足要求的走法。因此n=4k时必存在满足要求的走法。 n=4k+1与4k+3呢？ 其实，我们可以把它们分开为三部分——4k部分，1部分，3部分。 其中1部分能接在4k部分的B端（如上图），3部分能接在4k部分的A端（如下图） 因此，n=4k+1与4k+3时，都存在满足要求的走法。 下面证明n=4k+2时不存在满足要求的走法。 要证明这个命题，需先证明下面三个命题： n=2时不存在满足要求的走法； 不存在n×n（n不是4的倍数）的循环节； 不存在不需要循环节（尤其是4×4）的走法。 命题（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时为循环节。 若n=5，我们不妨以引入国际象棋中的黑白格。 第一步——（1,1）——黑格 第二步——（2,3）或（3,2）——白格 第三步——黑格 第四步——白格 第五步——黑格 而（5,4）与（4,5）皆为白格，第五步不能到达，所以5*5不会是循环节。 若n=6，则更不可能是循环节。 若n6，则n-15。我们取前五行和前五列讨论。 第一步——（1,1） 第二步——（2,3）或（3,2）。以（3,2）为例。 第三步——（2,4）或（4，4）或（5,3） 若第三步为（2,4），则第四步为（4,3）或（4,5）。若第四步为（4,3）则形成了4×4循环节，最后必会形