在\(n\times n\)的棋盘上,每个格子里画着一个箭头,指向它的八个相邻格子之一(如果格子位于边缘,箭头也可以指向棋盘外)。但相邻格子(包括对角相邻)里的箭头方向之差不得超过\(45^\circ\)。
一只旅鼠从棋盘中央的某个格子出发,沿着箭头一格一格地走。它是否注定要掉下棋盘?
是的,它必定会掉下棋盘。
一句话概括:旅鼠若被困住,就得绕一个环走一圈,那么箭头方向总共要转\(360^\circ\);但棋盘没有洞,箭头方向绕任何回路的总转动都是\(0^\circ\)。两者矛盾。
假设旅鼠永远不掉下去。棋盘有限,它迟早会重复走到某个格子,之后就一直绕同一个环转下去。所以只要证明“环不存在”。
第一,环上方向必须总共转\(360^\circ\)。 环上每格的箭头都指向环上的下一格,所以箭头方向就是前进方向。绕环一圈回到起点,方向也回到原样——但“方向回到原样”只说总转角是\(360^\circ\)的整数倍(\(0^\circ,\pm360^\circ,\pm720^\circ,\dots\)),并不等于\(0^\circ\):就像原地转一整圈,最后朝向没变,却确实转了\(360^\circ\)。究竟是哪个倍数,要看有没有真的绕一圈。环是不自交的闭合曲线(两步若在格心交叉,会逼出两个相邻格子的箭头相差\(90^\circ\),不允许),沿它走一圈就是绕了一圈,所以总转角是\(\pm360^\circ\),而不是\(0^\circ\)。
第二,任何回路方向的总转动都是\(0^\circ\)。 把八个方向编号\(0,1,\dots,7\)(相邻编号差\(45^\circ\))。从任一格子出发沿路走,每走一步就记下方向编号的变化(只能是\(-1,0,+1\)),累加起来。这个累加值只与终点有关、与路线无关:棋盘没有洞,任何闭合路线都能拆成一个个小方格,而绕一个小方格走一圈时,四个格子的箭头两两相差不超过\(45^\circ\),累加恰好是\(0\)。所以沿任何闭合回路走一圈,累加值回到原值,总变化是\(0\)。
两者矛盾(\(0\ne\pm360^\circ\)),所以环不存在,旅鼠必定掉下棋盘。
附:最小环的说法。 假设真有棋盘能困住旅鼠,取一个围住面积最小的环\(C\)(不妨设顺时针)。只留\(C\)和它围住的内部,把所有箭头顺时针转\(45^\circ\)——每个箭头转同样多,规则仍满足。\(C\)顺时针时,“前进方向顺时针转\(45^\circ\)”指向内部,于是\(C\)上的箭头都朝里,旅鼠进得去出不来;里面地方更小,他迟早绕出更小的环,与\(C\)最小矛盾。
棋盘一共只有\(n^2\)个格子。若旅鼠永远不掉下去,它就会无限地走下去,于是走过的\(n^2+1\)个格子中必有重复。取最早被重复到达的那个格子,从它第一次被访问处开始,之后的路线会原封不动地重演,于是旅鼠进入一个环:
\[ s_0\to s_1\to\cdots\to s_{m-1}\to s_0,\]
其中\(s_0,\dots,s_{m-1}\)是\(m\)个互不相同的格子,\(s_{i+1}\)正是\(s_i\)里的箭头所指的格子(下标按\(m\)取模)。注意\(m\ge 3\):一个格子不可能指向自己(\(m=1\));两个格子互相指(\(m=2\))要求两个箭头方向相反、相差\(180^\circ\),也违反规则。
所以,只要能证明这样的环不存在,旅鼠就必定掉下棋盘。
先看环上的每条边:第\(i\)条边是从\(s_i\)到\(s_{i+1}\)的“一步”,只有八个可能方向,而且这个方向恰好就是\(s_i\)里箭头的方向。
两条这样的“一步”边要在中间(而非端点)相交,唯一的可能是同一个\(1\times 1\)小方格的两条对角线。设这个小方格的四个角是左下\(A\)、右下\(B\)、左上\(C\)、右上\(D\),则两条对角线分别是\(A\)与\(D\)相连、\(B\)与\(C\)相连。两条对角线各有两种走向,共四种情形,每一种都会逼出一对相邻格子,使它们的箭头相差\(90^\circ\):
- \(A\to D\)与\(B\to C\):\(A\)朝右上、\(B\)朝左上,\(A\)与\(B\)左右相邻,相差\(90^\circ\);
- \(A\to D\)与\(C\to B\):\(A\)朝右上、\(C\)朝右下,\(A\)与\(C\)上下相邻,相差\(90^\circ\);
- \(D\to A\)与\(B\to C\):\(D\)朝左下、\(B\)朝左上,\(D\)与\(B\)上下相邻,相差\(90^\circ\);
- \(D\to A\)与\(C\to B\):\(D\)朝左下、\(C\)朝右下,\(D\)与\(C\)左右相邻,相差\(90^\circ\)。
四种情形都违反规则,所以环的两条边不可能在中间相交;又因为环上的格子互不相同(端点也不会重复),这个环一定是一条不自交的简单闭曲线。
关键一步:把方向“拉直”成普通的实数。
把八个方向按顺序编号\(0,1,2,\dots,7\)(相邻编号相差\(45^\circ\))。规则“相邻格子的箭头夹角不超过\(45^\circ\)”也就是说:相邻格子的编号在圆周上相差不超过\(1\)。
因为棋盘是一块“没有洞”的区域(单连通),可以给每个格子\(s\)再配一个整数\(\psi(s)\),称为它的展开角度,使得
- \(\psi(s)\)与编号同余,即\(\psi(s)\equiv k(s)\pmod 8\),其中\(k(s)\)是格子\(s\)的编号;
- 相邻格子的\(\psi\)值之差正好是它们夹角的带符号版本:\(\psi(s')-\psi(s)\in\{-1,0,1\}\)。
为什么一定配得出来?从任一格子出发,沿相邻格子一路走过去,每走一步就把这一小段的方向差(取\(\{-1,0,1\}\)中与编号差同余的那个值)累加起来,作为到达格子的\(\psi\)值。关键结论是这个累加值与所选路径无关:棋盘没有洞,任何闭合路线都可拆成许多“小方块”和“小三角形”,而绕一个小方块或小三角形走一圈时,涉及的几个格子两两相邻,箭头都落在\(45^\circ\)范围内,方向差累加恰好抵消为\(0\)。既然绕任何闭合路线的总差都是\(0\),\(\psi\)就良定义了。
沿环走一圈,每从\(s_i\)到\(s_{i+1}\),方向的变化就是\(\psi(s_{i+1})-\psi(s_i)\),它属于\(\{-1,0,1\}\),即\(-45^\circ,0^\circ,+45^\circ\)三者之一。把一圈的转角全加起来:
\[ \sum_{i=0}^{m-1}\bigl(\psi(s_{i+1})-\psi(s_i)\bigr)=\psi(s_0)-\psi(s_0)=0,\]
因为\(\psi\)是每个格子上确定的一个数,绕一圈后回到原值,相邻两项首尾相消。
也就是说,旅鼠绕这个环走一圈,方向总共转了\(0^\circ\)。
另一方面,一条不自交的简单闭曲线,沿它走一圈时方向必定恰好转过一整圈,总转角为\(+360^\circ\)或\(-360^\circ\):因为它把平面分成“里面”和“外面”,绕一圈必然刚好环绕一周。
于是同一个环给出两个互相矛盾的结果:总转角既是\(0^\circ\),又必须是\(\pm360^\circ\)。
所以这样的环根本不存在,旅鼠不可能被困住,它一定会掉下棋盘。
- 证明并未用到“从中央出发”这一点,也没用到棋盘的具体大小:只要棋盘有限、连成一片(没有洞),结论就成立。
- 一个容易让人上当的“局部”反例是八边形小环:让八个格子上的箭头依次指向八个方向,绕一圈正好转\(360^\circ\)。这个环本身看起来完全合法,但补上周围的格子时,总会在某个格子处被迫同时迁就相差\(90^\circ\)的两个邻居,从而违反规则——这正是“绕任何回路总转动为\(0\)”所抓住的全局约束。
- 换一种说法:把方向看作圆周上的点,则“相邻箭头相差不超过\(45^\circ\)”使箭头场成为一个\(1\)-利普希茨映射;棋盘单连通,故它可提升为实数的“展开角度”。环上的总转角等于展开角度绕一圈的净变化,而单值函数的净变化必为\(0\)——冲突来自“绕数(winding number)为\(0\)”与“简单闭曲线的绕数必为\(\pm1\)”这两件事不能同时成立。