题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
NZL Consider 2009 cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 50 consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. (a) Does the game necessarily end? (b) Does there exist a winning strategy for the starting player?
NZL 考虑一下 2009 年的卡片,每张都有一面金色的一面和一面黑色的一面,平行地放在一张长桌子上。最初,所有卡牌都显示出金色的一面。两名玩家站在桌子的同一条长边,以交替的动作进行游戏。每一步都包括选择一组 50 张连续的牌,其中最左边的牌显示为金色,然后将它们全部翻转,因此那些显示为金色的牌现在显示为黑色,反之亦然。最后能做出合法动作的玩家获胜。 (a) 游戏一定会结束吗? (b) 起始玩家是否存在获胜策略?
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2009 年 IMO Shortlist C1 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?