Question

Alice 和 Bob 玩如下游戏。他们面前有一堆 $n$ 个筹码。两人轮流操作，Alice 先手。每一轮，当前玩家从筹码堆中取走 $1$ 个或 $4$ 个筹码。取走最后一个筹码的玩家获胜。求不超过 $2024$ 的正整数 $n$ 的个数，使得无论 Alice 如何行动，Bob 都有保证获胜的策略。

Alice and Bob play the following game. A stack of $n$ tokens lies before them. The players take turns with Alice going first. On each turn, the player removes $1$ token or $4$ tokens from the stack. The player who removes the last token wins. Find the number of positive integers $n$ less than or equal to $2024$ such that there is a strategy that guarantees that Bob wins, regardless of Alice's moves.

答案

答案：809

知识点：组合游戏模运算小情形

难度评级：2110

解答：

若轮到行动的玩家在最优游戏下会输，就称 $n$ 为必败位置。我们断言必败位置正是 $n \equiv 0$ 或 $2 \pmod 5$ 。从这样的 $n$ 出发，取走 $1$ 个或 $4$ 个筹码会留下 $n \equiv 4, 1, 3 \pmod 5$ ，不会再次留下 $0$ 或 $2$ 。而从任何 $n \equiv 1, 3, 4 \pmod 5$ 出发，一步就能到达 $\equiv 0$ 或 $2 \pmod 5$ 的位置（分别取走 $1$ 、 $1$ 、 $4$ 个筹码）。由于 $n = 0$ 对轮到行动的玩家是败局，归纳可确认这个模式。

Bob 获胜当且仅当 $n$ 对 Alice 是必败位置。在 $1 \le n \le 2024$ 中， $5$ 的倍数有 $404$ 个，满足 $n \equiv 2 \pmod 5$ 的数有 $405$ 个（从 $2$ 到 $2022$ ），总共为 $404 + 405 = 809$ 。

Call $n$ a losing position if the player about to move loses with best play. We claim the losing positions are exactly $n \equiv 0$ or $2 \pmod 5.$ From such an $n,$ removing $1$ or $4$ tokens leaves $n \equiv 4, 1, 3 \pmod 5$ — never again $0$ or $2$ — while from any $n \equiv 1, 3, 4 \pmod 5$ one move reaches a position $\equiv 0$ or $2 \pmod 5$ (remove $1,$ $1,$ $4$ tokens respectively). Since $n = 0$ is a loss for the player to move, induction confirms the pattern.

Bob wins exactly when $n$ is a losing position for Alice. Among $1 \le n \le 2024$ there are $404$ multiples of $5$ and $405$ values $n \equiv 2 \pmod 5$ (from $2$ to $2022$ ), for a total of $404 + 405 = 809.$

2024 AIME I 第 3 题

答案：809

难度评级：2110

解答：

其他年份的第 3 题