MathLabs

第5题

蜗牛图尔博（Turbo）位于一个有2024行2023列的方格表的最上面一行，想要到达最下面一行。然而表中藏有2022只怪兽，除第一行和最后一行外，每一行恰好有一只怪兽，且没有两只怪兽位于同一列。图尔博会进行一系列尝试，从第一行走到最后一行。在每次尝试中，他可以选择第一行中任意一个格子作为起点，然后不断移动到与当前格子相邻（上下左右）的格子（允许回到之前访问过的格子）。如果图尔博到达一个有怪兽的格子，本次尝试立即结束，他会被送回第一行重新开始新的尝试。怪兽在各次尝试之间不会移动，并且图尔博会记住自己到过的每个格子里有没有怪兽。如果他到达最后一行的任意一个格子，本次尝试结束，图尔博获胜。试求最小的整数 nn，使得无论怪兽如何放置，图尔博都存在一种策略，能保证在至多 nn 次尝试内到达最下面一行。
第 4/5 步：M1在边缘的情形
上一步下一步
通俗地说

如果第一只怪兽紧靠着边界，图尔博改为沿着一条远离该边界的斜向阶梯路径前进；如果第二只怪兽挡住了这条阶梯路径，那么已经走过的安全部分，再结合两只怪兽已知的列位置，就能让图尔博在下一次尝试中构造出绕开两者的路线。

M1 on the edge  ⟹  staircase, then a third attempt around M2M_1 \text{ on the edge} \implies \text{staircase, then a third attempt around } M_2
详细分析

设 M1=(2,1)M_1=(2,1)；位于右边界的情形是镜像的。第2次尝试时，从第2行的 (2,2)(2,2) 进入，访问 (2,3)(2,3) 后返回 (2,2)(2,2)，再下到 (3,2)(3,2)。对每个 r=3,…,s−2r=3,\ldots,s-2，从 (r,r−1)(r,r-1) 进入，访问 (r,r)(r,r) 与 (r,r+1)(r,r+1)，返回 (r,r)(r,r)，然后下到 (r+1,r)(r+1,r)。在最后一个有怪兽的行，进入 (s−1,s−2)(s-1,s-2)，访问 (s−1,s−1)(s-1,s-1)，再下到目标行。这就是阶梯路径。若它畅通，图尔博在第2次尝试获胜。若在向下进入 (r,r−1)(r,r-1) 时首次遇到 M2M_2，则已经访问过的肩部格 (r−1,r)(r-1,r) 是安全的；第3次尝试沿安全前缀走到该肩部，从 (r,r)(r,r) 进入第 rr 行，向西走到第1列，再沿第1列下行。若在水平移动中遇到 M2M_2，则它正西边紧邻的格子安全；重走前缀到该格子，在第 rr 行向西走到第1列并下行。两种情形中，第 rr 行的其余格子都安全，因为该行唯一的怪兽就是 M2M_2；第1列在第2行以下安全，因为它已经含有 M1M_1。因此第三条路径必定到达目标。这样就得到了一个完全明确且至多使用3次尝试的策略。