几个简单的博弈问题

lulijie

至于大于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

哇~LS的好详细啊~

lulijie

把(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

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

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

lulijie

(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

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

lulijie

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

tm__xk

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