题目描述:
给定一堆共n >= 1个石头,现在有Alice和Bob按照以下规则玩游戏:
- 若某堆石子个数为
k > 1,那么可以将其分为两堆,其对应个数为i + j = k, i >= 1 && j >= 1 - 如果某一玩家操作之后,没有一堆石子可分,即最终共
n堆石子,每堆只有一个石子时,TA将获胜?
两人都以最佳策略轮流进行分堆且Alice先手,求证:当n为某特定值时,某一玩家必定赢比赛?
我的思路:找规律
- 当
n = 1时,Alice无法分堆,因此输了比赛。 - 当
n = 2时,Alice直接分为两堆,每堆各一个石头,因此赢得比赛。 - 当
n = 3时,Alice只能分为(1, 2)(不必考虑顺序,结果都是一样的),即一堆一个石头,一堆两个石头,那么Bob回到n = 2状态,因此Alice输了比赛。 - 当
n = 4时,Alice有分为(1, 3)或(2, 2)两种策略。Alice选择(1, 3),Bob面临n = 3必定失败,因此Alice赢得比赛。Alice选择(2, 2),Bob只能将其中一堆n = 2分为两堆(1, 1),然后剩下一堆n=2,因此Alice赢得比赛。
- 当
n = 5时,Alice有分为(1, 4)或(2, 3)两种策略。Alice选择(1, 4),Bob面临n = 4必定胜利,因此先手玩家输了比赛。Alice选择(2, 3),Bob有对n = 2的堆和对n = 3的堆进行划分共两种选择。(#1,应该是最佳)Bob选择对n = 2堆划分,那么Alice回到n = 3状态输了比赛。(#2)Bob选择对n = 3堆划分为(1, 2),那么Alice面临(2, 2)状态一定会输了比赛。(#3)
问题:
虽然可以找规律猜n为奇数时,先手玩家Alice必输,但是我没法证明,请问奆佬们这个可以用公式表达吗?先谢谢大佬了。
评论 (5)


