Fibonacci博弈

Problem

两个人进行Fibonacci博弈,若先手要有必胜策略,求他第一次至少要取多少个?

Solution

由Fibonacci博弈可知,如果当前石子数是fibonacci数,则先手必败,所以此时当前的先手必须全部取走

齐肯多夫(zeckendorf)定理:任何一正整数都能拆成一堆互不相同的正整数的和,且一定存在一种取法取到不超过它的最大Fibonacci数

1+