几个简单的博弈问题

lulijie

按照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个轮到后取方取，后取方无数可取。

lulijie

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落在同一区间，那么是必败局面，若不在同一个区间则是必胜局面。
                                    .........

lulijie

先取方的目标就是造成必败局面。
对于两堆的情况(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个，变成必败局面。

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 编辑 ]

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}必败局面。

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 编辑 ]

lulijie

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