【数学】石头博弈游戏

或许你接触过如下问题

1。 有n堆石头每堆石头有若干颗,两人互取。一次只能在一堆中取。
可取1到全部取完此堆任意。定取最后一次者获胜,问有何必胜的明智取法。为说明问题今再举一例

2。 有n排石头,每堆石头有若干颗。两人互取,一次只能在一排中取相邻两颗,取了一次后可能将此排分为两排。如一排原有11颗子,某人取第6、7颗,则此排被分为两排,其子个数分别为5,4。若一排子个数为一,则此排取不动。定能取最后一次者获胜,
问何为明智的必胜取法。

先界定一些名词 :
问题1中每一堆称为一个元素,用此堆石子个数n描述。
若干堆组成一个集合用(a1、a2、……、an)描述 。

问题2中每一排称为一个元素用此排石子个数n描述。
若干排组成一个集合用(a1、a2、……、an)描述,对任意给定集合用穷举展开法,理论上容易确定两人的理智取法。但我们要得如何快速得到理智取法。

再阐述一个概念:
一个集合A的下一步走法集Next(A):是指A的下一步走法的所有情况。如:
问题1中:Next( (2,3) )={ (1,3),(3),(2,2),(2,1),(2) }
问题2中:Next( (4,5) )={(2,5),(1,1,5),(4,3),(4,1,2)}

下面阐述本文最重要的概念: 集合X的等效值 |X|
等效值是用递归方法定义,

1:若Next(A)不存在则|A|=0,
问题1中:Next( (0) )不存在 则 |(0)|=0;
问题2中:Next( (1) )不存在 则 |(1)|=0,(再如|(1、1、……、1)|=0)

2:若Next(A)存在记
Next(A)={ a1,a2,……,an },next(A)={ |a1|,|a2|,……|an| }
则: |A|=min{x| x不属于next(A),x为非负整数}

问题1中:
next( (1) )={ |0| }={0} 可得 |(1)|=1。
next( (2) )={ |0|,|1| }={0,1}可得 |(2)|=2。
next( (1,1) )={ |1| }={1}可得|(1,1)|=0。
…………………………………………

问题2中:
next( (2) )={ |0| }={0} 可得 |(2)|=1。
next( (3) )={ |1| }={0}可得 |(3)|=1。
next( (4) )={ |(1,1)|,|(2)| }={0,1}可得|(4)|=2。
next( (2,1) )={ |(1)| }={0}可得|(2,1)|=1。
next( (5) )={ |(2,1)|,|(3)| }={1,1}可得|(5)|=0。
…………………………………………

现在或许你已经发现等效值已经能确定理智走法。
若一集合的等效值非0,那么先走的人必获胜。
因为他总能找到下一步使该下一步等效值为0。
而后走的人面对等效值为0时总不能找到下一步使该下一步等效值为0。
这样先走之人总面对等效值非0,后走之人总面对等效值为0。
直至先走的人获胜。
同理若一集合的等效值为0,那么先走的人必获败。
现在已经知道了等效值能确定理智走法。但等效值按定义算起来太麻烦。
下面介绍一个计算等效值的公式。

定义集合的加法为:
若 A=(a1,a2,……,an),B=(b1,b2,……,bm);
A+B=(a1,a2,……an,b1,b2,……bm);
定理1: |A+B|=|A|^|B| (^为异或符号)
证明:
先证 |A|^|B| 不属于next(A+B)
用数学归纳法:若A,B子数之和小于k时成立。
A,B子数之和等于k时有一例外

|A1+B|=|A|^|B| A1属于Next(A) 或
|A+B1|=|A|^|B| B1属于Next(B)
而由归纳法可得
|A1+B|=|A1|^|B| –>|A1|^|B|=|A|^|B| –>|A1|=|A| 此与等效值定义矛盾
同理|A+B1|=|A|^|B| B1属于Next(B)亦不可能
再证 x<|A|^|B| 时 x属于next(A+B)
若x<|A|^|B|则
x^|A|<|B|, x^|B|<|A| 总有一式成立
不防设 x^|A|<|B| 那么存在B1属于Next(B)且|B1|=x^|A|;
于是由归纳法可得
x=|A+B1|属于next(A+B)
由等效值定义得:
|A+B|=|A|^|B|
证毕。
容易推出问题1的等效值为 |(n)|=n;

当初始集合为(3,6,9)时
|(3,6,9)|=|(3)|^|(6)|^|(9)|=3^6^9=12>0 先拿获胜 拿法为
(3,6,9) –>(3,6,5) 因为 |(3,6,5)|=3^6^5=0.
问题2的前10个元素的等效值为(从(1)开始):
0,1,1,2,0,3,1,2,0,3

From 武汉白云黄鹤站

大学生数学竞赛题汇编
大学生数学竞赛题
高中数学联合竞赛试题
国际象棋中的趣题妙解
数学家俱乐部
数学趣题汇编
牛顿:在海边寻找贝壳的人
凯尔文:是上帝创造了生命,并且掌管一切
陆地动物能变成鲸吗
数学界的奇人妙事
趣味逻辑学问题

Conway: 游戏人生
有关孪生素数的一个有趣猜想
素数之恋-伯恩哈德·黎曼
等分布理论简介
数学家波利亚
物理学之神奇的数
鸟和青蛙
超级圆周率π运算器
数学难题汇编

此条目发表在数学, 游戏分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。