Loading...

Nim 取石子游戏的一些变种

November 19th, 2009 Leave a comment Go to comments

大家都知道正常的Nim游戏是取完最后一个赢. 必胜态是各堆石子异或值不为0. 现在来看看几个有意思的变种.

变种1: 取到最后一个石子的人输.
首先明确奇数个1是必败态, 偶数个1是必胜态. 这与正常的Nim不一致.
若只有一堆的个数大于1, 那么现在可以控制全场的1个数的奇偶性, 所以是必胜的. 这与正常的Nim一致.
若不止一堆的个数大于1, 由于不能转移到全是1的状态, (可能可以转移到仅有一堆大于1的状态, 但此状态与正常Nim一致), 所有当前可以转移到的状态的胜负性都是与正常的Nim一致的, 所以当前状态的胜负性与正常的Nim也是一致的.
综上, 除了全是1的状态胜负性跟正常的Nim不一致, 其余的状态胜负性与正常的Nim一致.

变种2: 只能从最左或最右的一堆中取, 取到最后一个的赢.
对于 [L,X,R] 状态, 若其是必败状态, 那么|L-R|<=1.
证明: 设[L,X,R]是必败态且R<L-1, 那么, 对于任何的1<=L’<L, [L',X,R]是必胜态. 那么对于每个L’, 都存在R’<R使得[L',X,R']是必败态, 显然不会出现[a,X,b]和[a',X,b]同为必败态的情况, 但L’有L-1个取值, R’却没有L-1个取值, 所以对于任意必败态[L,X,R], 都有|L-R|1则是必胜态, 否则, 由[X]的胜负性以及L-R的值可以推导出[L,X,R]的胜负性.

Share and Enjoy:
  • Google Bookmarks
  • del.icio.us
  • Facebook
  • FriendFeed
  • Twitter
  • 豆瓣
Categories: Brainstorm, Informatics Tags:
  1. No comments yet.
  1. No trackbacks yet.