题目求助|石子分堆问题求助(`n > 1` 即可分堆)

2354
发布于 未知归属地

题目描述:
给定一堆共n >= 1个石头,现在有Alice和Bob按照以下规则玩游戏:

  1. 若某堆石子个数为k > 1,那么可以将其分为两堆,其对应个数为i + j = k, i >= 1 && j >= 1
  2. 如果某一玩家操作之后,没有一堆石子可分,即最终共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)