MathLabs

第5题

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

当第一只怪兽位于内部时，阶梯路径可以向最近的边界推进，并在每个可能的第二只怪兽上方保留一个安全的肩部格。知道第二只怪兽的位置后，图尔博横穿它所在的行，进入第一只怪兽所在的已知安全列。

M1 interior  ⟹  a staircase reaches the safe column of M1M_1 \text{ interior} \implies \text{a staircase reaches the safe column of }M_1
详细分析

令网格的行号为 1,…,s1,\ldots,s、列号为 1,…,s−11,\ldots,s-1，其中 s=2024s=2024，并设 M1=(2,j)M_1=(2,j) 且 1<j<s−11<j<s-1。若 j=2j=2，就使用向右的镜像阶梯；否则使用下面的向左阶梯。从第2行第 j−1j-1 列进入，向西走到第 j−2j-2 列，下到第3行，再向西一列并下行，如此继续；在第 rr 行首次到达的格子为 (r,j−r+1)(r,j-r+1)，下行前先向西一步。这条路到达 (j,1)(j,1)。若向下进入 (r,d)(r,d) 时那里是怪兽 M2M_2，则它右上方的格子 (r−1,d+1)(r-1,d+1) 已经安全访问过。第3次尝试时，沿着安全前缀重走，从 (r,d+1)(r,d+1) 进入第 rr 行，再沿该行横向走到第 jj 列。如果是在向西移动时遇到 M2M_2，那么同一行中它右边紧邻的格子已安全，也可使用同样的横向绕行。由于 M2M_2 是第 rr 行唯一的怪兽，该行其余格子都安全；第 jj 列在第2行以下也安全，因为它已经含有 M1M_1，而每列至多一只怪兽。于是沿第 jj 列下到最后一行即可。如果阶梯无阻到达 (j,1)(j,1)，就在第 jj 行向东扫到第 jj 列再下行；扫行时遇到的任何怪兽就是 M2M_2，可沿同一行绕过，而第 jj 列不可能有怪兽。其中 rr 表示当前行。