【一】

Alice和Bob要从2堆石子里取石子,每一回合玩家可以从一堆里取出1个,也可以两堆都取出一个,没有石子者失败。若Bob先手,他是否有必胜策略?

【二】

表示当前状态:第一堆有个,第二堆有个。

显然游戏没有和局的情况,那么对于每个点,要么必胜,要么必败。

首先易得是必败点,这似乎没有必要证明什么。

又:可以一步走到必败点的,一定是必胜点(即使对手面临必败点);

所以是必胜点。

又:一步只能到达必胜点的是必败点(对手会使自己到达必败点):

对于,显然只能走到,所以是必败点。而$(0,3)$可以走到$(0,2)$使对方必败,所以$(0,3)$是必胜点。以此类推有$(0,2k)$是必败点,$(0,2k+1)$是必胜点。

若要使对手面临$(0,2k)$,显然$(1,2k+1)$和$(1,2k)$均能一步走到,故这2个点都是必胜点,即$(1,0)$到$(1,∞)$都是必胜点。

因为$(2,2)$只能走到$(1,k)$,所以$(2,2)$必败,则$(2,3)$$(3,3)$必胜。同理$(2,4)$必败,则$(3,4)$必胜。

再次推广,可得:

  • $(2k,2k)$必败
  • $(2k,2k+1)$必胜
  • $(2k+1,2k)$必胜
  • $(2k+1,2k+1)$必胜

【三】

Alice和Bob要从3堆石子里取石子,每一回合玩家可以从某堆里取出任意个,没有石子者失败。若Bob先手,他是否有必胜策略?

【四】

一个我并不会证明的结论:

仍然设$(x,y,z)$表示状态,当且仅当:x xor y xor z=0是必败点,否则是必胜点。

推广一下:

有n堆石子,当且仅当:a xor b xor c xor d xor ...=0是必败点,否则是必胜点。

(上文中的xor表示异或运算)

最后更新: 2018年11月24日 07:36

原始链接: https://ruixiangjiang.github.io/2018/11/09/stone-games/

× 请我吃糖~
打赏二维码