第五版杀拉五题串烧

21457

4.
从前有两个无聊的小孩，他们在地上玩石子。
第四天，他们两个人把地上的石子分成了N堆。
每一堆石子都有若干颗，将第i堆的石子数量记为xi；
他们商量好轮流操作，操作的规定是：
将某一堆中的至少一个石子，拿出来，任意分给其他堆，或者丢弃。
A先移动，B后移动。
轮到谁没有石头时，他便判输。

问一开始的N堆石头{x1,x2,x3...xi...xN}为什么情况时，A有必胜法？
（比如：有N=5堆石子时，这五堆分别为{10,12,13,10,15}）


由于可能发生两人将石子来回移动而导致无法分出胜负。
故定义，没有石子的状态为必败态；
从必胜状态操作一步之后一定有办法变成一种必败状态，从必败状态操作一步之后一定没办法变成必胜状态；
但是可以变成另一种必败状态，题目要求判断初态是必胜还是必败。


由于可能发生两人将石子来回移动而导致无法分出胜负。
故补充：
从
{A,b1,b2...bN,c,d,e...}
变化到
{A-a1-a2...-aN-a',b1+a1,b2+a2...bN+aN,c,d,e...}(a'为丢弃的石子数)
的这个操作
新增要求：
1.A>max{b1,b2...bN}
2.A>=a1+a2...aN+a'
3.A>max{b1+a1,b2+a2...bN+aN}
4.b1,b2...bN非零

42929

当{xi}=1，i=奇数，A稳赢；i=偶数，B稳赢。
比如，n=2时，xi>=2，A先移动，拿出第一堆的一个石子放在第二堆里面。B后移动，拿出第二堆的一个石子放在第一堆里面。这样不是死循环了吗？

21457

瞄一声，怎么突然这里没人了

22568

引用

将某一堆中的至少一个石子，拿出来，任意分给其他堆，或者丢弃。

意思是能不能只分掉一部分然后丢掉剩下的?

22568

4.求lz分析下4堆1122的话是谁赢.

39051

一个问题，某个石子堆空了之后，可以把其他石子堆的石子放进去吗

22568

4.
记某局面有N堆,数量为0<a[1]<=a[2]<=...<=a[N-1]<=a[N].
记L为所有使得2|N,a[1]=a[2],a[3]=a[4],...,a[N-1]=a[N]的局面.
(显然

引用

局面恰好可以分成若干组使得每组都是数量相同的两堆

为L中局面通俗的等价说法.)
我们将证明L即败局集.

I.
对一个L中的局面进行操作,若取石子的堆本来有k个,根据新增规则,
i.原先多于k个的堆在操作后不变;
ii.原先恰有k个的堆在操作后不变,除了取出石子的堆减少了;
iii.原先少于k个的堆在操作后仍然少于k个.
综上,操作后恰有k个的堆恰好比操作前少1.
显然L中局面中某数量的堆的数量必为偶数,故L中局面经操作后不在L中.

II.
对一个不在L中的局面0<a[1]<=a[2]<=...<=a[N-1]<=a[N],我们证明可以进行操作使得操作后局面属于L.
不妨设a[N-1]<a[N],否则不断将最多的两堆无视掉,直至剩下的堆中最多的两堆不一样多或只剩不足两堆:
每次无视掉的都是一样多的两堆,若剩下的堆可操作为L中局面,那么加上被无视的堆后显然仍为L中局面.
i.2|N-1
取走a[N],同时将a[1],a[3],...,a[k-2]分别增加为a[2],a[4],...,a[N-1].
增加的堆最多变为a[N-1]<a[N],
增加的石子总数为(a[2]-a[1])+(a[4]-a[3])+...+(a[N-1]-a[N-2])=a[N-1]-(a[N-2]-a[N-3])-(a[N-4]-a[N-5])-...-(a[3]-a[2])-a[1]<a[N],
为合法操作.
显然此操作后的局面属于L.
ii.2|N
将a[N]取走a[N]-a[1]变为a[1],同时将a[2],a[4],...,a[N-2]分别增加为a[3],a[5],...,a[N-1].
增加的堆最多变为a[N-1]<a[N],
增加的石子总数为(a[3]-a[2])+(a[5]-a[4])+...+(a[N-1]-a[N-2])=a[N-1]-(a[N-2]-a[N-3])-(a[N-4]-a[N-5])-...-(a[4]-a[3])-a[2]<a[N]-a[1],
为合法操作.
显然此操作后的局面属于L.

综上,L即为此博弈的败局集.

21457

第四题由天马行空答对

结论是当当前状态石子堆的数目成对出现时，该状态为必败的情况。
例如：{1,1,4,4,15,15,245,245,245,245,1123,1123}情况，被称为成对出现的情况。

首先，{0,0,0,0,0,0...0}为必败的情况。
对于状态{a1,a2,a3,a4...aN}而言，假定a1<=a2<=a3...<=aN
那么情况L便是：
a1=a2;a3=a4...aN-1=aN；
这样的情况在一次后，显然无法到达另一种状态L。原因是，如果操作了ai这一堆，如果ai=a(i+1)的话，那么a(i+1)必定无法和另一堆组成“一对”。
所以，必败态无法转移成必败态。

对于非必败态的情况{a1,a2,a3,a4...aN}，假定a1<=a2<=a3...<=aN
如果N为奇数：
将不成“一对”的石子数目最多的堆中的全部石子取出，分到其他各堆中，让其他各堆组成一对。
可行性：给a1堆添加(a2-a1);给a3堆添加(a4-a3)...
合计给其他堆的石子数为：(a2-a1)+(a4-a3)+...(a(N-2))-a(N-1)
显然这个数字是小于aN的
所以该操作可行。
如果N为偶数：
将不成“一对”的石子数目最多的堆中的(aN-a1)个石子取出，分到其他各堆中，让其他各堆组成一对。
理由如上，aN的石子数目足够。

所以，对于任何一个非必败态的状态而言，一定有一种操作将状态转移为必败态。

所以，“石子堆的数目成对出现”为这个游戏的必败态。

56203

这小孩这么无聊？

22568

(坐等下题