Skip to content

Nim问题

Published: at 04:06

前置

例题

大意:给定 nn 堆石子和每堆石子是数量,两个人轮流取,每次取的数量无上限,至少取一个,求是否存在先手必胜策略。

思路

考虑两堆石子的情况

两堆石子数量不相等

先手玩家先取石子多的那堆,使两堆石子数量相等,然后模仿后手玩家操作即可必胜。此时存在先手必胜策略

两堆石子数量不相等

先手玩家取石子后,后手玩家模仿先手玩家操作即可。此时不存在先手必胜策略

考虑三堆及更多石子的情况

启发:似乎与堆的数量与石子数量的奇偶性有关。 例题:考虑一个四堆的 Nim 问题,四堆石子数量分别为 7,9,12,157,9,12,15。 想法:二进制表示石子数量,得到:

23=82^3=822=42^2=421=22^1=220=12^0=1
堆70111
堆91001
堆121100
堆151111

结论

nn 堆石子的数量异或和等于 00 时,先手必胜,否则先手必败。