Question

Arjun 和 Beth 玩一个游戏：他们轮流从若干堵砖墙中的一堵移走一块砖，或移走两块相邻的砖；移走后产生的空隙可能形成新的砖墙。每堵砖墙都只有一块砖高。例如，大小为 $4$ 和 $2$ 的一组砖墙可以通过一步变成以下任意一种： $(3,2)$ 、 $\ (2,1,2)$ 、 $\ (4)$ 、 $\ (4,1)$ 、 $\ (2,2)$ 或 $(1,1,2)$ 。

Arjun 先手，移走最后一块砖的玩家获胜。对于哪一个初始配置，Beth 有必胜策略？

Arjun and Beth play a game in which they take turns removing one brick or two adjacent bricks from one “wall” among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes $4$ and $2$ can be changed into any of the following by one move: $(3,2),$ $\ (2,1,2),$ $\ (4),$ $\ (4,1),$ $\ (2,2),$ or $(1,1,2).$

Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?

$(6,1,1)$

$(6,2,1)$

$(6,2,2)$

$(6,3,1)$

$(6,3,2)$

答案：B

知识点：组合游戏不变量

难度评级：2390

小提示：

计算长度为 $n$ 的单堵砖墙的 Grundy 值，其中一步可以移走 $1$ 块或 $2$ 块相邻砖，并可能把砖墙分裂

Compute the Grundy value of a single wall of length $n,$ where a move removes $1$ or $2$ adjacent bricks and may split the wall

大提示：

Beth（后手）获胜当且仅当各堵砖墙 Grundy 值的异或为 $0$ 。

Beth (the second player) wins exactly when the XOR of the walls’ Grundy values is $0$

解答：

把每堵砖墙看作一个类似 Nim 的堆，并赋予 Grundy 值。一步移走 $1$ 块或 $2$ 块相邻砖，可能把一堵墙分成长度为 $a,b$ 的两堵。因此， $g(n)$ 是所有满足 $a+b=n-1$ 或 $a+b=n-2$ 的 $g(a)\oplus g(b)$ 的最小未出现非负整数。

从 $g(0)=0$ 开始，这个递推给出 $g(1),g(2),\ldots,g(6)$ 依次为 $1,2,3,1,4,3$ 。

后手 Beth 获胜当且仅当各墙 Grundy 值的异或为 $0$ 。检查每个选项，只有 $(6,2,1)$ 给出 $g(6)\oplus g(2)\oplus g(1)$ $=3\oplus 2\oplus 1=0$ 。

所以正确答案是 B。

Treat each wall as a Nim-like heap with a Grundy value. A move removes $1$ or $2$ adjacent bricks, possibly splitting a wall into lengths $a,b.$ Thus $g(n)$ is the mex of $g(a)\oplus g(b)$ over $a+b=n-1$ or $a+b=n-2.$

Starting with $g(0)=0,$ this recurrence gives $g(1),g(2),\ldots,g(6)$ equal to $1,2,3,1,4,3,$ respectively.

The second player Beth wins exactly when the XOR of the walls’ Grundy values is $0.$ Checking each option, only $(6,2,1)$ gives $g(6)\oplus g(2)\oplus g(1)$ $=3\oplus 2\oplus 1=0.$

Thus, the correct answer is B.

2021 AMC 12B Spring 第 22 题

答案：B

难度评级：2390

小提示：

大提示：

解答：

其他年份的第 22 题