乒乓球问题

mathe

我们还是以gxqcn那个100个乒乓球问题作为最基本版本，都假设是两人游戏:

i) 给定n个乒乓球，每次每人允许拿1到k个乒乓球，拿到最后一个乒乓球的输，那么应该采用什么策略才能尽可能的赢。（如果拿到最后一个的算赢呢？）

ii) 给定m堆乒乓球，每次每人允许从某一堆中拿任意多个乒乓球，拿到最后一个乒乓球的输，请问应该采用什么策略才能尽可能的赢。（如果拿到最后一个的算赢呢？）

iii) 给定m堆乒乓球，每次每人允许从某一堆中拿不超过k个的乒乓球，拿到最后一个乒乓球的输，请问应该采用什么策略才能尽可能的赢。（如果拿到最后一个的算赢呢？）

iv) 给定m堆乒乓球，每次每人可以挑选一堆乒乓球将它分成两堆（这分出来的两堆都必须含至少一个乒乓球），最后没有乒乓球堆可分的人赢，请问应该采用什么策略才能尽可能的赢。（如果没堆可分的算输又如何呢？）

v) 给定m堆乒乓球，每次每人可以挑选一堆乒乓球将它分成至少两堆（这分出来的每堆都必须含至少一个乒乓球），最后没有乒乓球堆可分的人赢，请问应该采用什么策略才能尽可能的赢。（如果没堆可分的算输又如何呢？）

vi) 给定n个排成一条直线的乒乓球，每人每次允许拿走1~k个相邻的乒乓球，拿到最后一个乒乓球的输，那么应该采用什么策略才能尽可能的赢。（如果拿到最后一个的算赢呢？）

vii) 给定若干排乒乓球，每排含乒乓球若干（数目可以各不相同),每人每次可以从某一派中拿走若干相邻的乒乓球，拿到最后一个乒乓球的输，那么应该采用什么策略才能尽可能的赢。（如果拿到最后一个的算赢呢？）

无心人

单一堆的，只要保证别人最后拿
策略可能只能对初始拿的人有效

假设m = n mod (k+1) > 0
假设一开始拿m－1个
后面的人不管拿多少， 比如i个
我们只要拿k+1-i个
准赢
如果m = 0，则可能输吧

无心人

同上的问题
如果保证拿到最后一个
则一开始拿n个就可以了

如果是别人拿，
那减去他拿的，得到新的数量，

如果m = n mod (k+1) > 0
则有上面策略
否则准输

shability

除了第一个，后面的每个都够想半天的
第二题第一问：
ii) 给定m堆乒乓球，每次每人允许从某一堆中拿任意多个乒乓球，拿到最后一个乒乓球的输，请问应该采用什么策略才能尽可能的赢。
m=2时，如果两堆球一样多(均大于1)，先拿必败，否则必胜
方法是始终让两堆球保持个数相同。
最后必然剩下(2,2)
(如果拿最后一个赢，也是如此)
m=3时，如果有两堆球个数相同，先拿必胜(方法是抓光不相同的一堆，如果相同的两堆球数为1，则是抓不相同的一堆至剩1个球)，否则策略是时刻保持有三堆球，且三堆的球各不相同，且设法让对手不得不让两堆球的个数相同或者是无法保持三堆球
具体的还没考虑好，但是结果必然是三堆球逐渐逼近(1,2,3)

mathe

这一类问题有一个统一的名称，叫Nim游戏，对于它们，有一个统一的解决方案，通常可以通过计算机解决（而一些较好的情况可以用公式表示）
对于这一类问题，都是有游戏双方参与博弈，双方轮流参与，而且双方使用的操作都相同。而博弈的操作对象可以分成若干组（也可以只有一组，组的数目在操作过程中可以发生变换），而参与者每次只能操作一组，而对所有的组允许的操作都是类似的。
当然，游戏是要求能够终止的，通常操作对象中有一个数目，所以操作过程要求这个数目是递减的（这样就可以保证操作总会终止）。

对于这样的问题，我们通常可以通过先仅考虑一组的问题，进而推广到任意组的情况。
首先，对于这类问题，由于必然终止，所以对于每个局面，要么是先手胜，要么是先手输。
我们处理的过程总是将所有一组的局面从简单到复杂排序，然后从最简单的局面出发，依次处理到更加复杂的局面
首先我们总是能够找到一个最简单的先手输的局面，我们将它记为状态0。（如果还存在比它更加简单的先手赢的局面，记为局面1）
然后我们从这个局面以后依次处理更加复杂的局面。
对于每个局面，我们记录下这个局面通过一次操作后可以到达的所有状态，我们将第一个不在这个状态集中出现的整数作为这个局面的状态。
通过这种方法，我们可以对于每个局面产生一个状态数（不同局面可以有相同的状态）。
而数学分析结果是一个局面先手赢的充分必要条件是它对应的状态数不是0。

比如对于第一个问题，我们首先知道只有一个乒乓球的局面先手输，所以一个乒乓求对应状态0.
为了简化问题，我们再添加一个没有乒乓球的局面（这个局面表示最后一个球被对手拿走了），所以可以记为状态1
而对于两个乒乓球的情况，先手可以通过拿到一个乒乓求到达状态0和状态1，所以记为状态2
...
同样对于k个乒乓球的局面，对应状态k
对于k+1个乒乓球的局面，可以到达状态0（取k个球),但是无法到达状态1，所以这个局面属于状态1。
而对于k+2个乒乓球，由于无法到达状态0，所以属于状态0。
对于k+3个球，得出属于状态2
...
我们可以得出它们的状态是一个周期为k+1的周期函数，其中模k+1为1的时候对应状态0。也就是这是先手输的充要条件。

mathe

前面给出的是只有一组操作数据时候的分析方法。
那么如果有多组数据的时候该怎么办呢？
非常另人吃惊的是结论非常简单，
如果现在有h组数据，各组局面对应的状态分别为$s_1,s_2,...,s_h$
那么我们可以定义总体的状态为$s=s_1"^"s_2"^"..."^"s_h$
那么结论就是先手输的充分必要条件是总体状态为0.

那么对于第二个问题，由于这时候模数k变成无穷大了，所以对于没一组，x(x>0)的局面对应的状态就是s(x),
其中s(x)在x是1时为0，不然就是x.
(但是x=1时对应0),所以对于m组，数目分别为$x_1,x_2,...,x_m$的情况
我们可以得到只有$s(x_1)"^"s(x_2)"^"..."^"s(x_m)=0$时先手才输。

mathe

同样对于问题"iv"我们也可以用类似的方法计算各种局面的状态，只是由于只是后组的数目会发生变化，计算过程中，一组情况对应的状态的计算需要用到多组情况的状态情况的组合（也就是通过状态数的异或来组合）

无心人

你怎么翻了老帐了阿

mathe

迟早要翻的吧