已知:有 $n$ 堆石子,最开始每堆有 $2$ 个石子,两人依次从中取出石子,每次可以取出一堆中任意个剩下的石子,每取三次将添加一堆新的石子,个数为 $2$。双方均采取最优策略,最后无法操作的人失败。
求证:当 $n \bmod 3=2$ 时,后手必胜,否则先手必胜。
根据题目描述和规则,我们来证明这个结论:当 ( n \bmod 3 = 2 ) 时,后手必胜;否则先手必胜。
每次操作可以选择一堆中的任意个剩余的石子,每取三次将会添加一堆新的石子数为 2。
观察操作的影响:
每三次操作后会新增一堆石子,即石子堆数 ( n ) 可能会增加。
数学归纳法证明:
基础情形: - 当 ( n = 2 ) 时,即开始只有两堆石子,每堆两个石子。先手无法操作,因此后手必胜。
归纳假设: - 假设对于所有 ( n < k ) 成立: - 如果 ( n \bmod 3 = 2 ),则后手必胜; - 如果 ( n \bmod 3 \neq 2 ),则先手必胜。
归纳步骤: - 考虑 ( n = k ) 的情况。
**情况分析**: - 如果 \( k \bmod 3 = 2 \): - 先手在第一次操作后,石子堆数变为 \( k-1 \)。根据归纳假设,此时后手面对 \( k-1 \) 堆石子,后手必胜。 - 如果 \( k \bmod 3 \neq 2 \): - 不论先手如何操作,先手总能控制最后一步的操作,使得后手面对 \( k \bmod 3 = 2 \) 的情况。因此,先手必胜。
这样,我们完成了对题目要求的证明。