巴什博弈

只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个,最后取光者得胜。

当(n-1)%(m+1)==0时后手胜利。

威佐夫博奕

有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

当且仅当局势为奇异局势时先手败,前几个为:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20),通式为(ak = [k(1+√5)/2],bk = ak + k)

简证:任意一奇异局势不能与前面bk - ak 差相等,否则两堆同减即转移到奇异局势。ak不能与之前任意奇异局势有相同数,否则另一堆减即可转移到奇异局势。

Fibonacci博弈

有一堆个数为n的石子,游戏双方轮流取石子,满足:先手不能在第一次把所有的石子取完,之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。 约定取走最后一个石子的人为赢家。

当n为Fibonacci数时,先手必败。其余先手胜。

简证:归纳证当n为Fibonacci数时,先手必败。齐肯多夫定理:任何正整数可以表示为若干个不连续的Fibonacci数之和。先手先取掉一个Fibonacci数大小的堆,后面每一个堆自己都是后手能取掉最后一颗,则先手胜。

Nim博弈

有n堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

所有堆大小异或为0则后手胜,否则先手胜。

简证:基于位。

SG

类似nim。游戏和的SG值为各游戏SG值的异或和。SG(x) = mex(S),mex表示最小的不属于这个集合的非负整数(可以取0),S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c),那么SG(x) = mex{SG(a),SG(b),SG(c)}。

树的删边游戏

给出一个有N个点的树,有一个点作为树的根节点。游戏者轮流从树中删去边,删去一条边后,不与根节点相连的部分将被移走。无路可走者输。

叶子节点的 SG 值为 0,中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和。

results matching ""

    No results matching ""