[算法]估计大家nim游戏看的差不多了，做道题吧!

Iambitious

一堆石頭有n個，兩人輪流取石，每次每人至少取一個，最多取上次對方取走石數的三倍。最後取光的贏得遊戲。當然，第一個拿的人不可以第一次就取光所有石頭。

第一问：
当1 <= n <= 100
结果为何
第二问：
当1 <= n <= 1000
结果为何
第三问：
当1 <= n <= 1000000
结果为何

大家来讨论讨论阿，第三问我也不确定阿。

yuhch123

f(0)=1
f(1)=2
f(2)=3
f(3)=4
f(4)=6
f(n)=f(n-1)+f(n-4) (n>=5)
对于所有的f(n)先手必败，否则先手必胜。
貌似是这样的吧。。。

Iambitious

呵呵，看来应该是这样了，用程序验证了一下，在3000以内都是正确的，但是不知道如何证明。

Iambitious

其实这道题我的本意是前两问可以用dp来解决，然后根据得出的结果找到规律，再解决第三问，不过虽然找到规律，但是却无法证明，比较失败。

yuhch123

证明比较麻烦，我大致讲一下好了，应该对的吧。
先证明，f(n)先手必败，f(0)~f(4)这5个手工验证，然后用数学归纳法。
假设已经证明f(0)~f(n)都是先手必败，也就是说后手可以保证拿到最后一个，而f(n+1)=f(n)+f(n-3)，这里可以证明3*f(n-3)>=f(n)>=9/4*f(n-3)（也可以用数学归纳法证明，此处略），那么我可以假想这f(n+1)个石子是由2堆组成的，第一堆是f(n-3)，第二堆是f(n)，并且保证从第一堆开始拿，每次可以拿任意多，第一堆拿完了，拿第二堆。那么，假如先手第一次就把第一堆拿完了，那么后手就可以一下子把剩下的拿完（3*f(n-3)>=f(n)）。否则，根据假设，后手定可以拿到前f(n-3)个石子中的最后一个，并且最后拿的一次最多拿了f(n-3)*3/4，那么先手就不能一下子就拿完第二堆（f(n)>=9/4*f(n-3)）。再根据假设，又可以得到后手可以拿到后f(n)个石子中的最后一个，也就是全部的最后一个。那么f(n+1)后手必胜，也就是先手必败。
再证明除了f(n)，先手必胜。一个结论：任何一个数可以表示为若干个f(n)的和，并且任意f(i),f(i+1),f(i+2),f(i+3)中至多只有一个出现(i>=1)，并且f(0),f(1),f(2)中至多只有一个出现，这个可以用数学归纳法证明。又一个结论：3*f(n-4)<f(n)然后设x不是f(n)中的数，那么x=f(a1)+f(a2)+f(a3)+...+f(an)(a1<a2<a3<a4<...<an)，并满足上面的条件，先手只需要第一步拿掉f(a1)个石子，然后后手第二步一定不可能直接拿掉f(a2)个，因为3*f(n-4)<f(n)。那么根据前面的证明，就可以得出这f(a2)个石子中的最后一个一定是由先手拿走的。3*f(a2)<f(a3)，因此这f(a3)个石子后手也不能一次拿完，然后这f(a3)个石子中的最后一个，也是由先手拿走。如此如此。。。f(an)中的最后一个也是先手拿的。因此对于x不是f(n)中的数，先手必胜。

Iambitious

形式化证明如下：
由性质：
1.f(n+1)=f(n)+f(n-3)
2.对于f(n),最后一次最多取３/４f(n)
3.f(n)<=3f(n-3)
4.f(n)>=9/4f(n-3)
根据数学归纳法可以证明：
状态(f(n), a),a<f(n)为安全状态
再证明(n, n-1)对于所有的n!=f(m)为非安全状态

Iambitious

1.证明：
根据数列定义可得
2.证明：
反证法:假设最后一次可以提取mf(n)个石子(m>3/4)那么，前一次所提取的石子数为
m/3f(n)，但是4/3mf(n)>f(n)与已知总共有f(n)个石子矛盾，所以原假设不成立
所以原命题得证。
3.4证明：
（1）当n=5时，成立
（2）假设n=k时也成立，即9/4f(k-3)<=f(k)<=3f(k-3)那么n=k+1时

2. f(k+1)=f(k)+f(k-3)
3.      <=3f(k-3)+3f(k-6)
4.      =3f(k-2)
5. f(k+1)=f(k)+f(k-3)
6.      >=9/4f(k-3)+9/4f(k-6)
7.      =9/4f(k-2)

复制代码

综上所述原命题得证

Iambitious

证明：
（1）当n=5时，成立
（2）假设当n<=k时也成立，那么n=k+1时：
对于f(k+1)=f(k)+f(k-3)，第一次所取石子数为a
(i)当a>=f(k-3)时，由性质3可以知道，后手必能一次取完所有石子，因为3f(k-3)>=f(k)
(ii)当a<f(k-3)时，由于假设条件结论对n<=k都成立，所以后手必然可以使先手达到(f(k),x)状态.
又因为x<=3/4f(k-3)，而f(k)>=9/4f(k-3)所以f(k)>=9/4f(k-3)>x，所以(f(k),x)也是安全状态。

综上所述，(f(n),a),a<f(n)为安全状态。

Iambitious

参见yuhch123的证明，说的很清楚了，也就是通过选取一定的石子必然使后手进入
安全状态。如何选择n的表示方法呢，就是对于n,先找n所能容纳的最大的f序列中的数f(m)，然后n=n-f(m),再继续此过程，这样得到的表示才是唯一的，并且符合所需的性质。

yuhch123强人一个阿，而且才16岁，难得难得，佩服佩服!

ak70

还是不太明白原题，假设n=100,第一人第一次拿98，那么第二人可以拿2，这时第二人赢。如果第二人拿1，那接下来第一人再拿1则第一人赢。楼主是否忘了什么条件？