|
发表于 2006-8-9 12:30:18
|
显示全部楼层
证明比较麻烦,我大致讲一下好了,应该对的吧。
先证明,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)中的数,先手必胜。 |
|