火柴游戏...《算法艺术与信息学竞赛》
有n根火柴，甲乙两人轮流从中拿取，一次至少拿一根，至多拿先前对方一次所取火柴数目的两倍。甲先拿，开始时甲可以拿任意数目的火柴（不能拿完）。最先没有火柴拿的一方为败方。给定一个n，问甲能否赢！(1<n<=10^9）
[解决办法]
以前看过这个问题，如同1楼所说，就是斐波那契数列，如果是这个数列中的数，先手输，否则先手赢。
赢的方法就是拿掉若干根，使之成为斐波那契数列中对应的项（最接近的一项）。
[解决办法]
想了一下，不是Fibonacci数列，答案应该是n=k*(k-1)/2+2 k=1,2,3,...的时候先走必败，其他情况先走胜
证明如下：
定义函数f(n, m)表示当前有n根火柴，且对手上一步取了m根的情况下，有没有必胜法，若有f=1，否则f=0
若是第一次走，另m=0，其他情况m都不为0
则n=2时 f(2, 0)=0, f(2,m)=1 m>=1 表示若共有2根火柴，先走的人必败，若是当前有2根火柴，且对手上一次取了1根或以上，当前先走的人必胜
依次类推：
f(3,0)=0 f(3,1)=0, f(3,m)=1 m>=2
f(4,m)=1 m>=0
……………………
发现2个规律：
1. 一旦f(n,m)=1, 那么右边的当n不变m增大时f的值都为1
2. 一旦f(n,0)=0, 则必须等到f(n,ceiling(n/2))的时候才为1
先走必败的a_k的序列为：2, 3, 5, 8, 12, ....
即a_k-a_(k-1)=k-1
是一个二级等差数列
很容易求得表达式a_k=k*(k-1)/2+2
具体证明免了吧，很容易用归纳法出来
[解决办法]
1L和2L是对的，确实是Fibonacci数列，证明是对6L的改进：
定义函数f(n, m)表示当前有n根火柴，且对手上一步取了m根的情况下，有没有必胜法，若有f=1，否则f=0
若是第一次走，令m=0，其他情况m都不为0。 n是从2开始的，为了叙述方便，补充n=0和1时的定义： f(0, m)=0, f(1, m)=1 m>=1。无需定义f(1,0)和f(0,0)
对一个固定的n，必须是f(n,1), f(n,2), ..., f(n,ceiling(n/2)-1)都为0, 则f(n,0)才为0。否则f(n,0)=1。
n=2时 f(2,m)=1 m>=1 得出f(2,0)=0. 表示若共有2根火柴，先走的人必败，若是当前有2根火柴，且对手上一次取了1根或以上，当前先走的人必胜
依次类推：
f(3,1)=0, f(3,m)=1 m>=2 则f(3,0)=0
f(4,m)=1 m>=0 则f(4,0)=1
……………………
算法是：f(n,m)=f(n-1,1) | f(n-2, 2) | ... | f(n-2m,2m) 然后取反
发现一旦f(n,m)=1, 那么右边的当n不变m增大时f的值都为1
推断f(n,0)=0的序列是Fibonacci数列
用归纳法来证明,假设n是一个Fibonacci数
有f(n, 1)=…=f(n, ceiling(n/2)-1)=0, f(n, ceiling(n/2))=1
我们发现f(n+1,m)=f(1,m), f(n+2,m)=f(2,m)......对任何m成立，也就是说f的值从头重复了一遍
但是f(n+1,0), f(n+2,0), ...都是1，因为对一个固定的n，必须是f(n,1), f(n,2), ..., f(n,ceiling(n/2)-1)都为0, 则f(n,0)才为0
第一次例外是f(n+k)，其中k也是一个Fibonacci数,满足k>n/2
而满足这个条件的第一个k就是n之前的那个Fibonacci数
所以n+k是n之后的第一个Fibonacci数
可能描述的不清楚，lz自己在稿纸上画画就能发现规律
[解决办法]
应该倒过来推导：
假设甲要赢，那么甲最后拿了之后剩几根火柴，无论乙怎么拿家都能赢。
假如剩了1根，那么乙拿了，甲输。
假如剩了2根。每次至少拿1根，可以是先前拿的2倍。那么乙可以拿2根，甲还是输。
假如剩了3根。如果甲先前拿了1根，那么无论如何，这次甲赢。其他，甲输。
假如剩了4根，如果甲先前拿了1根，无论如何，甲赢。
假如剩了5根，如果甲先前拿了1根，那么结果和上面两个一样。
假如剩了6根，如果甲先前拿了。。。
太复杂了，我大概总结了一下，似乎只要拿的火柴数目不超过三分之一，就能赢。
