MathLabs

第5题

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

图尔博在第2行第一次踏入的格子完全可能藏有怪兽，而在下一次尝试中，他在第3行第一次踏入的新格子也同样可能藏有怪兽，因此任何固定策略都无法避免两次失败。

n≥3n\ge3
详细分析

在图尔博的第一次尝试中，当他第一次踏入第 22 行的那一刻，对手完全可能已经在那里放置了一只怪兽，使这次尝试结束。在第二次尝试中，图尔博必须在某一列第一次进入第 33 行；对手同样可能已经在那里放置了怪兽。这说明任何策略都无法保证在少于 33 次尝试内取得成功，因此 n≥3n\ge3。