灯下 登录
番外 · 题谱 · 2021 · P14

2021 IMO Shortlist C6

组合 · P3/P6 · 压轴题

题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。

IMO Shortlist 2021 C6 combinatorics

A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share a side). The hunter wins if after some finite time either - the rabbit cannot move; or - the hunter can determine the cell in which the rabbit started. Decide whether there exists a winning strategy for the hunter.

一个猎人和一只看不见的兔子在一个无限的方格上玩游戏。首先,猎人用有限多种颜色固定细胞的颜色。然后兔子秘密地选择一个单元格作为起始位置。每分钟,兔子都会向猎人报告当前单元格的颜色,然后秘密地移动到它以前没有访问过的相邻单元格(如果两个单元格共享一侧,则它们是相邻的)。如果在一段有限的时间后,猎人获胜 - 兔子无法移动;或者 - 猎人可以确定兔子开始的牢房。决定猎人是否存在获胜策略。

提示 1

先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。

提示 2

找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。

提示 3

把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。

完整解答

这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2021 年 IMO Shortlist C6 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。

这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?