MathLabs

第5题

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

由于第2行只有一只怪兽,沿着这一行一直走到底(接受最终会失败)是在真正向下推进之前,摸清这只怪兽确切位置的最省力方式。

Attempt 1: sweep row 2 to find monster M1\text{Attempt 1: sweep row 2 to find monster } M_1
详细分析

在第一次尝试中,图尔博沿着整个第二行行走,直到到达位于那里的怪兽 M1M_1;这次尝试必然失败,但图尔博现在已经知道 M1M_1 所在的确切列。