魔方吧·中文魔方俱乐部

标题: 几个简单的博弈问题 [打印本页]

作者: zxl0714 时间: 2009-8-20 20:38:47 标题: 几个简单的博弈问题

1、有一堆石子，2个人轮流取，每次可取n至m个，先取完者胜。先取者应如何取才能尽可能保证自己胜利。
2、有两堆石子，2个人轮流去，每次可从其中一堆中取n至m个，先取完者胜。先取者应如何取才能尽可能保证自己胜利。

继续推广又如何呢？

作者: 业余魔术师 时间: 2009-8-20 20:53:48

第一题：让n小于石子数量，m大于石子数量就可以了。

[ 本帖最后由业余魔术师于 2009-8-20 20:55 编辑 ]

作者: 黑桃Q 时间: 2009-8-20 21:30:39

寒谁蹲在地上拿石子当棋

作者: tm__xk 时间: 2009-8-20 21:44:07

取不尽怎么办....题目没说清楚....

作者: zxl0714 时间: 2009-8-20 21:59:24

2楼的不是让你改变n和m。。。而是让你想一个取石子的策略。。。
4楼如何有取不尽的情况。。。

作者: 东莞的8 时间: 2009-8-20 21:59:57

1.设总数为X，用把X取m+n的模，设剩下a个，然后第一次取a-1（如果a=1就直接任意取），以后每次取的策略是对方取b个，先取者就取m+n-b个。
第2问用同样的策略，只是每次都取对方取完的那一堆。不知道这样可以不

作者: flwb 时间: 2009-8-20 22:26:13

假设两人都不犯错误,胜负不是由他们决定的,而是由开始一堆有多少石子所决定。

作者: tm__xk 时间: 2009-8-20 22:55:33 标题: 回复 5# 的帖子

每次可取n至m.
若剩下的少于n怎么办..

作者: zxl0714 时间: 2009-8-20 23:07:05

少于n就是最后取的赢。。。。就是说一开始如果石子数少于n个，后手赢

作者: tm__xk 时间: 2009-8-20 23:14:37 标题: 回复 9# 的帖子

就是说不能取就输..

作者: tm__xk 时间: 2009-8-20 23:23:27

第一题:
W={-1,-2,...,-m}mod(n+m)
L={0,1,...,n-1}mod(n+m)

作者: lulijie 时间: 2009-8-20 23:31:59

按照6楼的思路：
1. 设总数为X，X除以m+n的余数设为a，那么0<=a<n+m
如果a<n,那么先取方必败，先取方取b，那么后取方取m+n-b个，最后必剩下a个，先取方无数可取。
如果a>n，那么先取方必胜，
如果a>m，那么先取方第一次取m个，剩下a-m+k*(m+n)个，以后后取方取b个，先取方取m+n-b个，最后剩下a-m个轮到后取方取，后取方无数可取。
如果n<a<=m，那么先取方第一次取a-1个，剩下1+k*(m+n)个，以后后取方取b个，先取方取m+n-b个，最后剩下1个轮到后取方取，后取方无数可取。

作者: zxl0714 时间: 2009-8-21 00:00:50

11楼的对了。不过你这么写别人很难看懂吧。。。
12楼分析的比较透彻。那两堆的又如何呢？

[ 本帖最后由 zxl0714 于 2009-8-21 00:01 编辑 ]

作者: lulijie 时间: 2009-8-21 00:21:59

k堆石子的个数分别为a1，a2，......，ak。
用(a1，a2，......，ak)表示上述的局面。
－－－－－－－－－
设b1、b2、......，bk每个数都小于n+m
如果(b1，b2，......，bk)是必败局面（所谓必败局面，就是先取方必败），
那么将任意一堆或几堆石子增加n+m的整数倍的局面都是必败局面。
所以只要研究(b1，b2，......，bk)即可。
－－－－－－－－－－－－－－－－－
对于k＝2：(b1，b2)
如果b1<n，相当于第一堆不存在，就转化为b2一堆的情况，不用分析了。
如果b1>=n，且b2>=n，分析如下：
      如果b1<2n，且b2<2n ，那么必败。
      如果b1<2n，且b2>=2n ，那么必胜。
      如果b1>=2n，且b2>=2n ，那么再分为：
                     b1<3n，且b2<3n，必败
                     b1<3n，且b2>=3n，必胜
                     b1>=3n，且b2>=3n，再分为：
                                 ......
-------------------------------------------
也就是说，将0至n+m-1按照每n距离分成[0,n)、[n,2n)、[2n,3n)......若干个区间，
若b1、b2落在同一区间，那么是必败局面，若不在同一个区间则是必胜局面。
                                 .........

作者: tm__xk 时间: 2009-8-21 00:28:37

第二题:
从程序上看,败局在(n,m)平面上的规律如下

我懒得证了)
设m=qn+r,0<=r<=n-1.
以下提到的所有对角线均为从左下角到右上角....(大家能理解我说的吧..就不废话了..)
(1)作一个边长为n+m的正方形.
(2)将(q+1)个边长为n的正方形和一个边长为m的小正方形,依次放在(1)中的大正方形的对角线上.
(3)用这样的大正方形(包括其中的小正方形)不重叠地覆盖(n,m)平面的第一象限(含坐标轴).
这样,败局集合=小正方形集合.

就两堆来说,我和14L的答案一样.

其实我觉得推广堆数没什么意义..

[ 本帖最后由 tm__xk 于 2009-8-21 00:37 编辑 ]

作者: tm__xk 时间: 2009-8-21 00:29:59 标题: 回复 13# 的帖子

不好意思,以前混过竞赛,习惯了....

作者: lulijie 时间: 2009-8-21 01:00:44

先取方的目标就是造成必败局面。
对于两堆的情况(a1,a2)
取n+m的模，转化为(b1,b2) b1=a1 mod n+m，b2=a2 mod n+m
设k1=[b1/n]，k2=[b2/n] [ ]为取整
如果k1=k2，那么你就认命吧，必败。
如果k1、k2不等，假设k1<k2，那么取第二堆使得其剩下k1*n+1个，变成必败局面。

作者: 348307806 时间: 2009-8-21 10:53:41

这都什么破问题呀，什么说的都不清楚，直接先取的取完不就是胜了么？

作者: flwb 时间: 2009-8-26 20:42:50

首先请问楼主：是不是应该把“先取完者胜”改成“谁取到最后一颗胜”，不然的话，你的第二题中的“先取完者胜”是指一堆，还是两堆？

我按照谁取到最后的获胜来算：（M>N）

第一题：如果石子是N+M的整数倍或不是整数倍但余数大于M，是“必输局面”，你就认输。如果不是“必输局面”，你把它取成N+M的整数倍即可获胜。

第二题：

1：如果两堆石子都是“必输局面”，认输；

2：一是一不是，把不是的取成“必输局面”，现在该对手了，必胜；

3：都不是“必输局面”有些复杂，如果一堆石子除以N+M的余数小于≤N，而另一堆>N，必胜；如果余数都>N，必输；如果都≤N，也必输。

[ 本帖最后由 flwb 于 2009-8-26 20:49 编辑 ]

作者: zxl0714 时间: 2009-8-27 11:10:09

14楼能不能再分析一下三堆的情况？

作者: lulijie 时间: 2009-8-27 22:13:19

至于大于2堆的情况：我们先将每堆的石子数除以n+m，得到各堆的余数b1、b2、......，bk
只要研究(b1，b2，......，bk)即可
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
我们用{p1，p2，......，pk}来表示(b1，b2，......，bk)局面。
   其中b1∈[p1*n,(p1+1)*n)
         b2∈[p2*n,(p2+1)*n)
         ......
         bk∈[pk*n,(pk+1)*n)
比如n=2, 那么 {3，4，3，6}就表示第一堆石子数∈[6,8)，第二堆石子数∈[8,10)，
                                             第三堆石子数∈[6,8)，第四堆石子数∈[12,14)
如果每个pi值都小于10，那么可把逗号省略，如{3，4，3，6}可写成{3436}
任何一个pi等于0，都相当于该堆不存在。
－－－－－－－－－－－－－－－－－－－－－－－－－－－
那么必败局面如下：把大括号省略了。
0
11
22
33
44
55
66
77
88
123
145
167
246
257
347
356
1111
1122
1133
1144
1155
1166
1177
1188
1247
1256
1346
1357
2222
2233
2244
2255
2266
2277
2288
2345
2367
3333
3344
3355
3366
3377
3388
4444
4455
4466
4477
4488
4567
5555
5566
5577
5588
6666
6677
6688
7777
7788
8888
11123
11145
11167
11246
11257
11347
11356
12223
12245
12267
12333
12344
12355
12366
12377
12388
13345
13367
14445
14467
14555
14566
14577
14588
15567
16667
16777
16788
22246
22257
22347
22356
23346
23357
24446
24457
24556
24666
24677
24688
25557
25667
25777
25788
33347
33356
34447
34456
34557
34667
34777
34788
35556
35666
35677
35688
上述的结果是5堆以内，pk值都不大于8的所有必败局面。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
具体推导见下帖15楼和28楼的回复。不过本贴的必败局面(先手方必败）就是下帖所称呼的必胜局面（走成该局面就必胜），只是出发点不一样，实质上是一样的。
http://bbs.mf8-china.com/viewthread.php?tid=27412&;extra=page%3D9&page=1

[ 本帖最后由 lulijie 于 2009-8-27 22:21 编辑 ]

作者: mofangPYH 时间: 2009-8-27 22:14:57

哇~LS的好详细啊~

作者: lulijie 时间: 2009-8-27 22:39:13

把(b1，b2，...，bi，...，bk)局面表示成{p1，p2，...，pi，...，pk}，计算很简单：
只要将每个bi除以n，pi就等于它的整数部分，即pi＝[bi/n] ，  [ ] 表示整数部分。
－－－－－－－－－－－－－－－
比如n=2，m=5，石子数为（13，11，12）
因为n+m=7，所以先除以7，得到余数  (6,4,5)
因为 [6/2]=3，[4/2]=2，[5/2]=2，转化为 {322}
  因为322不是必败局面，所以它是必胜局面。只要除掉3，变成22必败局面即可。
回到(6,4,5)局面，将第一堆拿走5个石子，变成(1,4,5)必败局面，即{0，2，2}＝{2，2}必败局面。

作者: tm__xk 时间: 2009-8-28 00:50:20 标题: 回复 21# 的帖子

于是现在的问题是,任给一组(pi),如何简单判断....

[ 本帖最后由 tm__xk 于 2009-8-28 13:19 编辑 ]

作者: lulijie 时间: 2009-8-28 12:20:13

(ai)    一共k堆
↓
(bi)    bi=ai mod (n+m)
↓
{pi}    pi=[bi/n] [ ]表示取整
然后查表，若从表中找到{pi} ，那么是必败局面，否则必胜局面。
当k=1时，必败局面就只有p1=0
当k=2时，必败局面就是p1=p2
当k>2时，没有简单判断方法，不过可以事先制作必败局面的表（如21楼的表），然后根据{pi}查表。

[ 本帖最后由 lulijie 于 2009-8-28 12:21 编辑 ]

作者: zxl0714 时间: 2009-8-28 18:46:45

楼上的你再仔细观察一下必败局面，看看他们有什么共同点。我提示一下这个共同点跟二进制的位运算有关。

作者: lulijie 时间: 2009-8-28 22:06:15

明白了，楼上的规律就是所有的pi的异或运算等于0，则就是必败局面。
非常好的规律。

作者: tm__xk 时间: 2009-8-28 23:26:48

恍然大悟....把(ai)变成(pi)之后,就相当于取的上下限(n和m)都没有了....于是变成那个经典的博弈问题....
败局就是二进制不进位地相加后,每位均为偶数.
即如27L所说,异或为0.

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)