Nim Game

n堆石子, 两个人轮流操作, 每次可从任意一堆中取出任意多>0的石子, 无法操作者输.

• 结论 : 将所有石子数异或起来, 结果不为\(0\) , 先手胜; 反之, 先手负.
• 证明 :

1. 石子数都为 \(0\) 为必败态.
2. 若当前异或和为 \(0\) , 则无论怎么取, 取后异或和不为 \(0\) .
3. 若当前异或和 \(k\) (设最高位为 \(x\) ) 不为 \(0\) , 则必存在石子数 \(a_i\) 中位 \(x\) 为 \(1\) , 此时 \(a_i\;xor\;k .
   即取 \(a_i\;xor\;k\) 可使异或和为 \(0\) .

Nimk Game

n堆石子, 两个人轮流操作, 每次可从任意\(\small{\leq}\)k堆中取出任意多>0的石子, 无法操作者输.

• 结论 : 将所有石子数的每一位异或起来 \(mod\;(k+1)\) , 若结果都为 \(0\) , 先手负; 反之, 先手胜.
• 证明 :

1. 石子数都为 \(0\) 为必败态.
2. 若当前每一位的异或和都为 \(0\) , 则无论怎么取, 取后必存在某位的异或和不为 \(0\).
3. 若当前存在某位的异或和不为 \(0\) , 从高位往低位确定每堆石子取的个数.
   记 \(m\) 为当前位取 \(0,1\) 都可的堆数 ( 如果某为 \(1\) 的位取 \(0\) , 则比其低的位可随意取值 ) , \(n\) 为这一位除这 \(m\) 堆外, 当前位为 \(1\) 的堆数 \(mod\;(k+1)\) 的值.
   若 \(n+m\leq{k}\) , 则直接使这 \(n\) 堆此位取 \(0\) , 其他不变 , \(m=n+m\) 即可;
   否则 , \(n+m>k\) 即 \(n+m\geq{k+1}\) , 此时 \(n\geq{k+1-m}\) , 在这 \(m\) 堆 \(k+1-m\) 位取 \(1\) , 其余取 \(0\) ,其他不变即可.

Bash Game

n堆石子,两个人轮流操作,每次可从任意一堆中取出[1,m]个石子,无法操作者输.

• 结论 : 将所有石子数 \(mod\;(m+1)\) 异或起来,结果不为\(0\) , 先手胜; 反之, 先手负.

• 证明 :

1. 石子数都为 \(0\) 为必败态.
2. 若当前异或和为 \(0\) , 则无论怎么取, 取后异或和不为 \(0\) .
3. 若当前异或和 \(k\) (设最高位为 \(x\) ) 不为 \(0\) , 则必存在石子数 \(a_i\;mod\;(m+1)\) 中位 \(x\) 为 \(1\) , 此时 \(a_i\;mod\;(m+1)\;xor\;k .
   即取 \(a_i\;mod\;(m+1)\;xor\;k\) 可使异或和为 \(0\) .

Staircase Nim

n阶台阶, 每次可以从一个台阶上拿掉任意数量石子放到下一层台阶, 无法操作者输 ( 第1级可以往地面上放 ) .

• 结论 : 将所有奇数级异或起来, 结果不为\(0\) , 先手胜; 反之, 先手负.
• 证明 :

1. 台阶上石子数都为 \(0\) 为必败态.
2. 若当前奇数级异或和为 \(0\) , 则无论是移奇数级到偶数级还是移偶数级到奇数级, 取后异或和不为 \(0\) .
3. 若当前奇数级异或和为 \(0\) , 则移奇数级到偶数级后, 异或和不为 \(0\) .

Anti-Nim Game

Wythoff Game

Take & Break

推荐

http://www.cnblogs.com/Randolph87/p/5804798.html
http://blog.csdn.net/clover_hxy/article/details/53818624

2017-10-25 20:40:09