几个简单的博弈问题

tm__xk

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

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

zxl0714

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

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

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

tm__xk

第二题:
从程序上看,败局在(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

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

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个，变成必败局面。

348307806

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

flwb

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

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

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

第二题：

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

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

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

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

zxl0714

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