1、组合数学（一）李子星内容提要 组合游戏 巴什博弈 威佐夫博弈 尼姆博弈 有向图游戏与有向图游戏的和与 SG函数 反尼姆博弈与反组合游戏 继续探讨 ICG的和组合游戏组合游戏 （ Combinatorial Games），又称为“Impartial Combinatorial Games”（以下简称 ICG）。满足以下条件的游戏是 ICG：（ 1）有两人参与游戏，轮流做出决策，两人都最理性得追求胜利（ 2）两名选手交替做出决策，无法做出决策的人失败，然后游戏结束。（ 3）游戏总能在有限次决策后结束（ 4）游戏的同一个状态不会多次抵达（ 5）任意一个游戏者在某一确定状态可以作出的决策集合只与当前的
2、状态有关，而与游戏者无关组合游戏定义 “先手必败 ”状态（ 必败态 ），和 “先手必胜 ”状态（ 必胜态 ）：（ 1） 无法进行任何移动的局面是必败态；（ 2） 可以移动到必败态的局面是必胜态；（ 3） 所有移动都导致必胜态的局面是必败态。按照这个定义，如果局面不可能重现，那么每个状态或者是必胜态或者是必败态，而且可以通过定义计算出来。巴什博弈【 问题一 】有一堆 n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m个。取走最后一个物品的人获得胜利。问先手是否必胜。巴什博弈这显然是一个组合游戏问题对于一个状态，可以用当前的物品数 x来唯一描述。容易知道，对于一个状态 x，如果 x%(m+1)=0，那么这个状态肯定是必败态，否则是必胜态。巴什博弈设当前状态是 x： 如果 x=0，那么显然这是一个必败态 如果 x%(m+1)b2,a1b1。推论二：对于任意两个的必败二元组 (a1,b1)，(a2,b2)，有 b1-a1b2-a2。即，所有必败二元组的两元之差的绝对值必定各不相同。威佐夫博弈利用性质和推论，可以证明如下结论：“将必败二元组按首元为关键字排序，每个必败二元组中首元为未在前面的必败二元组中出现的最小正整数，并且第 N组中两个数差为N“。
