桌上放有 $n$ 根火柴，甲乙两人轮流从中取走火柴．甲先取，第一次可取走至多 $n-1$ 根火柴，此后每人每次至少取走一根火柴，但是不超过对方刚才取走火柴数目的两倍．取得最后一根火柴者获胜．问：当 $n=100$ 时，甲是否有获胜策略？请详细说明理由．
【难度】
【出处】
2010年全国高中数学联赛安徽省预赛
【标注】
【答案】
当 $n=100$ 时，甲有获胜策略
【解析】
把所有使得甲没有获胜策略的初始火柴数目 $n$ 从小到大排序为 $n_1$，$n_2$，$\cdots$．容易发现其前 $4$ 项分别为 $2$，$3$，$5$，$8$．下面我们用数学归纳法证明：
① $\{n_i\}$ 满足 $n_{i+1}=n_i+n_{i-1}$；
② 当 $n=n_i$ 时，乙总可以取到最后一根火柴，并且乙此时所取的火柴数目 $\leqslant n_{i-1}$；
③ 当 $n_i<n<n_{i+1}$ 时，甲总可以取到最后一根火柴，并且甲此时所取的火柴数目 $\leqslant n_{i}$．
设 $k=n-n_i$，$i \geqslant 4$．注意到 $n_{i-2}<\dfrac {n_i}{2}<n_{i-1}$．
当 $1 \leqslant k <\dfrac {n_i}{2}$ 时，甲第一次取 $k$ 根火柴，剩余 $n_i>2k$ 根火柴，乙无法获胜．
当 $ \dfrac {n_i}{2} \leqslant k < n_{i-1}$ 时，$n_{i-2}<k<n_{i-1}$，根据归纳假设，甲可以取到第 $k$ 根火柴，并且甲此时所取的火柴数目 $\leqslant n_{i-2}$．剩余 $n_i>2n_{i-2}$ 根火柴，乙无法获胜．
当 $k=n_{i-1}$ 时，设甲第一次取走 $m$ 根火柴，若 $m \geqslant k$，则乙可以取走所有剩下的火柴．若 $m<k$，则根据归纳假设，乙总可以取到第 $k$ 根火柴，并且乙此时所取的火柴数目 $\leqslant n_{i-2}$．剩余 $n_i>2n_{i-2}$ 根火柴，甲无法获胜．
综上可知，$n_{i+1}=n_i+ n_{i-1}$．
因为 $100$ 不在数列 $\{n_i\}$ 中，所以当 $n=100$ 时，甲有获胜策略．
① $\{n_i\}$ 满足 $n_{i+1}=n_i+n_{i-1}$；
② 当 $n=n_i$ 时，乙总可以取到最后一根火柴，并且乙此时所取的火柴数目 $\leqslant n_{i-1}$；
③ 当 $n_i<n<n_{i+1}$ 时，甲总可以取到最后一根火柴，并且甲此时所取的火柴数目 $\leqslant n_{i}$．
设 $k=n-n_i$，$i \geqslant 4$．注意到 $n_{i-2}<\dfrac {n_i}{2}<n_{i-1}$．
当 $1 \leqslant k <\dfrac {n_i}{2}$ 时，甲第一次取 $k$ 根火柴，剩余 $n_i>2k$ 根火柴，乙无法获胜．
当 $ \dfrac {n_i}{2} \leqslant k < n_{i-1}$ 时，$n_{i-2}<k<n_{i-1}$，根据归纳假设，甲可以取到第 $k$ 根火柴，并且甲此时所取的火柴数目 $\leqslant n_{i-2}$．剩余 $n_i>2n_{i-2}$ 根火柴，乙无法获胜．
当 $k=n_{i-1}$ 时，设甲第一次取走 $m$ 根火柴，若 $m \geqslant k$，则乙可以取走所有剩下的火柴．若 $m<k$，则根据归纳假设，乙总可以取到第 $k$ 根火柴，并且乙此时所取的火柴数目 $\leqslant n_{i-2}$．剩余 $n_i>2n_{i-2}$ 根火柴，甲无法获胜．
综上可知，$n_{i+1}=n_i+ n_{i-1}$．
因为 $100$ 不在数列 $\{n_i\}$ 中，所以当 $n=100$ 时，甲有获胜策略．
答案
解析
备注
