2021 AMC 10B Spring 第 24 题

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

小提示：

计算每个相关单独墙长的游戏值。

Compute the game value for a single wall of each relevant size

大提示：

当所有墙的游戏值按位异或为

0

时，轮到行动的玩家处于必败状态。

A position is losing for the player to move exactly when the xor of the wall values is

0

解答：

对长度为

n

的单独一堵墙，根据所有可能操作计算它的 Sprague-Grundy 值。这里用到的各个墙长的值为

\begin{aligned} &g(1)=1,\quad g(2)=2, \\ &g(3)=3,\quad g(4)=1, \\ &g(5)=4,\quad g(6)=3 \end{aligned}\text{。}

多堵墙的局面在这些值按位异或为

0

时，正好是轮到行动者的必败局面。逐一计算选项：

(6,1,1): 3\oplus1\oplus1=3\text{，}

(6,2,1): 3\oplus2\oplus1=0\text{，}

(6,2,2): 3\oplus2\oplus2=3\text{，}

(6,3,1): 3\oplus3\oplus1=1\text{，}

(6,3,2): 3\oplus3\oplus2=2\text{。}

只有

(6,2,1)

是轮到行动者的必败局面，所以 Beth 恰好在这个初始配置下有必胜策略。

所以答案是 B。

For a single wall of length

n,

compute its Sprague-Grundy value from the possible moves. For the wall lengths needed here, the values are

\begin{aligned} &g(1)=1,\quad g(2)=2, \\ &g(3)=3,\quad g(4)=1, \\ &g(5)=4,\quad g(6)=3. \end{aligned}

For several walls, the position is losing for the player to move exactly when the xor of the wall values is

0.

Evaluating the choices gives

(6,1,1): 3\oplus1\oplus1=3,

(6,2,1): 3\oplus2\oplus1=0,

(6,2,2): 3\oplus2\oplus2=3,

(6,3,1): 3\oplus3\oplus1=1,

(6,3,2): 3\oplus3\oplus2=2.

Only

(6,2,1)

is losing for the player to move, so Beth has a guaranteed win exactly for that starting configuration.

Thus, the answer is B .

2021 AMC 10B Spring 第 24 题

答案：B

难度评级：2390

小提示：

大提示：

解答：

其他年份的第 24 题