2010 年安徽预赛 · 第 12 题

解答

定义 $F_1=1,F_2=2,F_{k+2}=F_{k+1}+F_k$。每个正整数都可唯一写成互不相邻的若干 $F_k$ 之和：先减去不超过它的最大 $F_k$，余数小于 $F_{k-1}$，继续贪心即可。唯一性可由恒等事实“下标小于 $k$ 的不相邻项之和至多为 $F_k-1$”递归证明。记这一表示中的最小项为 $z(r)$。

先证明借位性质：若 $0<v<z(r)$，则

设 $z(r)=F_k$。将 $F_k-v$ 作贪心展开，不会与原来的更高项相邻，故只需证 $z(F_k-v)\le 2v$。$k=1,2$ 的情形直接成立。对更大的 $k$，若 $v\ge F_{k-2}$，则 $F_k-v<F_k$ 的最大项至多 $F_{k-1}\le 2F_{k-2}\le 2v$。若 $v<F_{k-2}$，则

后一个括号的最大项至多 $F_{k-3}$，可接在前项后；对 $k-2$ 应用归纳假设即得结论。

现在证明：余下 $r$ 根、本次最多可取 $m$ 根时，先手有必胜策略，当且仅当 $m\ge z(r)$。按 $r$ 强归纳：

若 $m\ge z(r)$，便取走 $z(r)=F_k$。若取尽则获胜；否则余数的最小项至少是 $F_{k+2}>2F_k$，对手上限为 $2F_k$，按归纳假设处于必败局面。

若 $m<z(r)$，任意合法取法 $v\le m$ 都有 $v<z(r)$。借位性质给出 $z(r-v)\le 2v$，而这恰是对手的上限，所以对手按归纳假设可以取胜。这也证明了两个方向。

本题

甲第一次取 $3$ 根（没有取尽，符合首次上限 $99$），留下 $97$ 根，乙至多取 $6$ 根，而 $z(97)=8>6$。因此