进阶≈ 15 分钟未开始

巴什博弈(取石子)

核心概念

巴什博弈:桌上有 $n$ 颗石子,两人轮流取,每次取 $1$ 到 $m$ 颗,取走最后一颗的人获胜。

结论:用 $m+1$ 去除 $n$ 。

巴什博弈的核心是制造一个"对手逃不掉的倍数"。关键数字是 $m+1$ :无论对手取 $1$ 到 $m$ 中的几颗,你总能补足成 $m+1$ 颗一组。

所以只要你能把局面变成"剩下的石子数是 $m+1$ 的倍数",就稳操胜券——对手取 $k$ 颗,你就取 $m+1-k$ 颗,每一轮合计减少 $m+1$ ,倍数关系始终保持,直到最后一组由你取完。先手要做的,就是第一步把零头 $n \bmod (m+1)$ 取掉,把"倍数"这个烫手山芋扔给对手。

巴什博弈

10 ÷ 4 余 2： 先手必胜,第一步取走 2 颗(绿色),使剩下 8 为 4 的倍数。

石子数 n10

每次最多取 m3

关键数是 m+1。先手只要取走零头,把剩余石子变成 m+1 的倍数,之后对手取 k 颗你就取 m+1−k 颗,稳赢。

例题 1判断先手胜负并给出走法

$10$ 颗石子,每次取 $1$ 到 $3$ 颗,取走最后一颗者胜。先手有必胜策略吗?

▸查看解答步骤

答: 先手胜,首取 2 颗

例题 2先手必败的局面

$12$ 颗石子,每次取 $1$ 到 $3$ 颗,先手能必胜吗?

▸查看解答步骤

答: 12 是 4 的倍数,先手败

$15$ 颗石子,每次取 $1$ 或 $2$ 颗,取最后一颗者胜,先手必胜。

$m+1=3$ , $15\equiv0\pmod3$ ,先手必败。

$10$ 颗石子,每次取 $1$ 到 $3$ 颗,先手第一步应取走几颗?

$10\bmod4 = 2$ ,取走 $2$ 颗使剩下 $8$ 为 $4$ 的倍数。

$20$ 颗石子,每次取 $1$ 到 $4$ 颗,先手必败。

$m+1=5$ , $20\equiv0\pmod5$ ,先手必败。

$13$ 颗石子,每次取 $1$ 到 $3$ 颗,先手第一步应取走几颗?

$13\bmod4 = 1$ ,取 $1$ 颗剩 $12$ ( $4$ 的倍数)。

前置知识点

—

接下来学习