博弈论
赶紧证明一下取石子游戏的必胜条件。
当 \(S=a_1 \oplus a_2 \oplus a_3...\oplus a_n=0\) 时,先手必败,反之必胜
首先当 \(a_1=a_2=...=a_n=0\) 时,先手必败,此时 \(S=0\) 。
当 \(S\ne0\) 时,必然能让 \(S=0\) 。
证明当 \(S\ne0\) 时,必然能让 \(S=0\) 。
- 首先对于 \(a_1 \oplus a_2 \oplus a_3...\oplus a_n=S\) ,只要 \(S\oplus S\) 即可变为 \(0\) 。
- 证明一定存在 \(a_i\) 通过减法可以变成 \(a_i\oplus S\) 即可。
也就是证明存在 \(a_i\) 使得 \(a_i>a_i\oplus S\) 。
找出一个最高位与 \(S\) 相等的数 \(a_i\) 即可。
当 \(S=0\) ,只能让 \(S\) 变成非 \(0\) ,因为此时此刻每次减法都会改变每一位的个数,只要有一位 \(1\) 的个数变成了奇数,那么便是 \(S\ne 0\) 。
因为必胜状态一定是 \(S =0\) 的,所以证毕。
阶梯博弈
考虑在一个有 \(n\) 层的阶梯上,每个阶梯上有很多个小球,每次可以把一个阶梯上的若干个小球放到下一个阶梯,地面上的小球不可触碰,无法移动
首先考虑全部都在偶数层阶梯上的情况,注意到如果我是先手,每次都只能把偶数层放到奇数层,如你所见,最底下是偶数,也就是第 \(0\) 层,而后手只要把所有奇数层转移到偶数层即可,最后肯定是他把东西都放到地面,此时先手必败。
那么当奇数层有的情况,其实就是看谁能把状态变成全部偶数的情况,此时此刻如果是我就考虑把奇数都移到偶数位置,此时此刻就相当于把奇数层的小球取出来,谁先取完即可。