PDF《在一个游戏问 题 的解 决中体验模式的应用》

3 列扑克 牌,第1列3张,第2列6张,第3列9张. 两人依 次轮流从中取走若干张扑克牌,每次只能在其中一 列中取,至少取

1 张,至多取完该列的所有扑克牌. 取到最后

1 张牌者为输. 若甲先取牌,如何保证自 己必赢? 为叙述方便,作如下书写约定:将3列扑克牌 数记为(3,6,9),某列中取走若干张牌后的结果也 仿此表述,例如甲从第

2 列取走

3 张牌后的结果记 为:甲(3,3,9),乙再从第

3 列取走

2 张牌后的结 果记为:乙(3,3,7);

并在某些场合称甲方为"我方",称乙方为"对手". 面对该问题的一个自然想法是先作些尝试. 比 如甲先将第

3 列的

9 张牌取完,即:甲(3,6,0),此 时乙只需应对:乙(3,3,0). 接着,若甲只取

1 张, 无论甲(2,3,0)还是甲(3,2,0)时,乙都从另一列 取1张,即得乙(2,2,0),至此,不管甲怎么取,乙 都可将最后

1 张留给甲,乙已经稳操胜券;

若甲取

2 张,比如甲(1,3,0),乙只需取走第

2 列的

3 张便 赢了;

若甲取

3 张,比如甲(0,3,0),则乙(0,1,0) 便赢了. 看来甲取完一列显然是失策的. 不过由上面的 分析可以发现:一方只要控制了(0,2,2),(0,3,3) 中的任何一种,便能稳操胜券,我们称它们为"无 解模式"(对于对手来说是无法破解的). 于是,我们得到了第一类无解模式:(0,n,n), 其中 n∈N +,且n≥2. 这3列中的

3 个数可以任意 调换,下文中的所有模式均如此. 至此,我们有了解 决这一问题的一个看起来很不错的思路,即"构建 模式": 1)先从最简单的开始,易发现(1,1,1)是无解 模式. 进而知(1,2,3)也是无解模式. 2)若我方(1,3,4),对手(1,3,2)即为无解模 式. 因此(1,3,4)不是无解模式. 3)若我方(1,4,5),对手(1,4,4)时,我方(0, 4,4)为无解模式;

对手(1,4,3)时,我方(1,2,3)为 无解模式;

对手取第

2 列时,可用同样的无解模式 破解. 因此(1,4,5)是无解模式. 4)若我方(2,4,6),对手(1,4,6)时,我方(1, 4,5)为无解模式;

对手(2,3,6)时,我方(2,3,1)为 无解模式(其实只要有两个数小于等于

3 时,一步 便可获得无解模式);

对手(2,4,5)时,我方(1,4, 5)为无解模式;

对手(2,4,4)时,我方(0,4,4,)为 无解模式;

对手的其他应对均极易破解. 因此(2, 4,6)为无解模式. 利用化归与分类,容易得到如下无解模式: (3,5,6),(1,6,7),(2,5,7),(3,4,7). 现在,我们来分析(3,6,9)的破解方法. 利用前面得到的无解模式,容易发现:只需在 第3列取走

4 张,即甲控制(3,6,5)这一无解模式 便赢定了. 当然,我们还想知道,除此之外是否还有其他 的取胜之道. 对此,我们只能进行详细地分类讨论: 若甲(2,6,9),则乙(2,6,4)为无解模式;

若甲(1, 6,9),则乙(1,6,7)为无解模式;

若甲(3,5,9),则乙(3,5,6)为无解模式;

若甲(3,4,9),则乙(3,4, 7)为无解模式;

若第

2 列牌数小于等于 3,由前面 的分析,极易被破解;

若甲(3,6,8)或(3,6,7),则乙(3,6,5) 为无解模式;

若甲(3,6,6),两列数相 同,则乙(0,6,6)或(3,5,6)均可破解;

若甲(3,6, 4),则乙(2,6,4)为无解模式;

若第

3 列的牌数小 于等于 3,同样极易被破解. 综上所述,我们确认:对于(3,6,9),甲欲赢得 游戏的唯一解是从第

3 列中取走

4 张,控制(3,6, 5)这一无解模式.

2 模式扩展 改变

3 列扑克牌的张数,将问题一般化. 为了 解决一般问题,需要将现有无解模式扩展,甚至构 建更一般的无解模式. 为此,我们对已有模式的特 征进行分析. 一个较为明显的特征是,已有模式中的大多数 均满足