Home Page
Search
\begin{md} # 巴什博奕 ## 问题 有一对物品共 N 个,两个人轮流从这堆物品中取出最少一个最多 K 个物品。 1. 取到最后一个物品的人获胜 2. 取到最后一个物品的人失败 分别分析这两种情况下先手,后手的获胜情况。 ## 分析 如果取到最后一个物品的人获胜,那么 1. N <= K 时,必定是先手获胜, 2. N = K + 1 时,必定是后手获胜 3. 当 N > K + 1 时,如果 N = (K + 1) * n (n 为自然数且 n > 1),那么不论先手取多少个物品(假设为 x 个),后手总是可 以取 y = (K + 1) - x 个物品,使得下一轮开始的时候物品总数保持为 K + 1 的倍数,最后一定是后手获胜。 4. 当 N > K + 1 时,如果开始时 N 不等于 K + 1 的倍数,那么先手第一次可以从物品中取出 m 个,使得 N - m 变为 K + 1 的倍数,这样子就回到了情况 3,但是先后手的顺序对调,最后一定是先手必胜。 所以,如果 N % (K + 1) = 0, 则后手胜,否则先手胜。 如果取到最后一个物品的人失败,那么 1. N = 1 时,必定是先手失败,后手获胜 2. 1 < N < K + 1 时,必定是后手失败,先手获胜 3. 当 N >= K + 1 并且 N = (K + 1) * n + 1 (n 为自然数且 n >= 1),那么不论先手取多少个物品(假设为 x 个),后手总是 可以取 y = (K + 1) - x 个物品,使得下一轮开始的时候物品总数保持为 (K + 1) * k + 1 (k 为自然数),最后一定是后手获胜。 4. 当 N >= K + 1 并且 N != (K + 1) * n + 1 (n 为自然数且 n >= 1),那么先手第一次可以从物品中取出 m 个,是的 N - m 变为 (K + 1) * n + 1 (n 为自然数),这样子就回到了情况 3,但是先后手的顺序对调,最后一定是先手必胜。 所以,如果 N = (K + 1) * n + 1 (n 为自然数), 则后手胜,否则先手胜。 \end{md}
Home Page