Game

Bash

$1$堆石子，$n$个， 每次每人能取$[1, m]$个石子，不能拿的输

conclusion

$(m + 1) \mid n$ 时，先手必败

$(m + 1) \nmid n$ 时， 先手必胜

prove

1. 当$n \le m$时， 先手可直接取走所有
2. 当$n = m + 1$时，先手无论取走多少个，后手都能取走剩下所有
3. 当$n = k \times(m + 1)$时，对于每$m+1$个石子，先手取$i$个，后手取的$m+1−i$个
4. 当$n = k \times (m + 1) + x (0 < x < m + 1)$时，先手取$x$个，局势回到上一种情况

Nim

$n$堆石子，每堆$a_i$个，每人每次能从一堆石子中取任意多个石子但不能不取，不能拿的输

conclusion

$\bigoplus\limits_{i = 1}^{n}a_i = 0 $时，先手必败

$\bigoplus\limits_{i = 1}^{n}a_i \neq 0 $时，先手必胜

prove

Wythoff

$2$堆石子，$x, y$个，每人每次能从任意一堆中拿任意数量的石子或在两堆石子中拿走相同数量的石子，不能拿的输

conclusion

$\lfloor {(y - x) \times \frac{1 + \sqrt{5}}{2}} \rfloor = x$ 或 $\lfloor {(x - y) \times \frac{1 + \sqrt{5}}{2}} \rfloor = y$时，先手必败

$\lfloor {(y - x) \times \frac{1 + \sqrt{5}}{2}} \rfloor \neq x$ 且 $\lfloor {(x - y) \times \frac{1 + \sqrt{5}}{2}} \rfloor \neq y$时，先手必胜

prove

Fibonacci

$1$堆石子， $n$个，先手第一次能取任意多个，但不能取完，以后每次取子数不能超过前一次取子数的2倍，不能拿的输

conclusion

$n = fib_i$时，先手必败

$n \neq fib_i$时，先手必胜

prove

ExNim

$n$堆石子，每堆$a_i$个，每人每次能从$[1, d]$堆石子中取任意多个石子但不能不取，不能拿的输

conclusion

二进制展开，设$cnt_{bit_i}$为某位为$1$的个数

$\forall i \quad (d + 1) \mid cnt_{bit_i}$时， 先手必败

$\exists i \quad (d + 1) \nmid cnt_{bit_i}$时，先手必胜

prove

Staircase Nim

$n$堆石子，每堆$a_i$个，每次每人可以把第$i(i > 1)$堆的任意个放到第$i - 1$堆里，或取第一堆任意个，不能拿的输

conclusion

$\bigoplus\limits_{i = 1}^{\lceil \frac{n}{2} \rceil}a_{2i - 1} = 0$时，先手必败

$\bigoplus\limits_{i = 1}^{\lceil \frac{n}{2} \rceil}a_{2i - 1} \neq 0 $时，先手必胜

prove