1737. 取石子游戏

n=1,2 下列出大量例子找规律,找出初步规律然后在 n=3,4 下验证规律,最后发现只有石子堆个数为偶数且都是 1sakiko ,否则都是 momoko

sum == n && n % 2 == 0

具体证明如下:

  1. [1]是momoko必胜,[1,1]是sakiko必胜
  2. 全为1时双方都只有一种取法,容易发现奇数个[1]最后一定是momoko取,momoko胜,同理偶数个是sakiko必胜
  3. [x](x>1)时,
    • 若x=2,momoko取2必胜;
    • 若x=3,momoko取1,sakiko只能取1,回到[1],[1]是momoko必胜
    • 若x=y(y是偶数,y>2),momoko取1,sakiko只能取1,回到x=y-2,不断如此操作,一定会到达x=2,此时momoko取2必胜;
    • 若x=y(y是奇数,y>3),momoko取1,sakiko只能取1,回到x=y-2,不断如此操作,一定会到达x=3,此时momoko取1,sakiko取1,momoko取1必胜。
    • 综上所述,[x]时,momoko必胜
  4. [a1, a2, a3, ...]时
    • 第一回合momoko对任意一个数按照(3)的方法取一次;
    • 在这之后,sakiko无论取哪个数,momoko都可以按照(3)的方法取一次;
    • 如果每个数都大于1,那么一定可以按照(3)的方法让momoko对每个数都是它最后取完的
    • 如果大于1个数字的数目是1,sakiko一定可以取完至少一次1。但是对不是1的数,按照(3)的方法,momoko至少存在一种策略,使得sakiko没有办法取完,所以只要在这a1,a2,a3...里存在不是1的数,momoko一定可以最后取完它

综上所述,当且仅当有偶数个1时sakiko必胜,否则momoko必胜。