除数博弈

爱丽丝和鲍勃一起玩游戏,他们轮流行动,爱丽丝先手开局。
最初,黑板上有一个数字N,在每个玩家的回合,玩家需要执行以下操作:

  • 选出任一x,满足0 < x < NN % x == 0
  • N - x替换黑板上的数字N

如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回true,否则返回false,假设两个玩家都以最佳状态参与游戏。

示例

输入:2 输出:true 解释:爱丽丝选择 1,鲍勃无法进行操作。
输入:3 输出:false 解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

题解

/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(n) {
    return n & 1 ? false : true;
};

思路

理解一下题意,查看了输入输出示例,推断这是一个通过判断奇偶性决定胜负的游戏。
这里引用官方推论:博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候,不妨试着写几项试试:

  • N = 1的时候,区间(0, 1)中没有整数是 n的因数,所以此时Alice败。
  • N = 2的时候,Alice只能拿1N变成1Bob无法继续操作,故Alice胜。
  • N = 3的时候,Alice只能拿1N变成2,根据N = 2的结论,我们知道此时Bob 会获胜,Alice败。
  • N = 4的时候,Alice能拿12,如果Alice1,根据N = 3的结论,Bob会失败,Alice会获胜。
  • N = 5的时候,Alice只能拿11,根据N = 4的结论,Alice会失败。
  • ......

写到这里,也许你有了一些猜想。没关系,请大胆地猜想,在这种情况下大胆地猜想是AC的第一步。也许你会发现这样一个现象:N为奇数的时候Alice(先手)必败,N为偶数的时候 Alice必胜。 这个猜想是否正确呢?下面我们来想办法证明它。
证明:N = 1N = 2时结论成立。
N > 2时,假设N ≤ k时该结论成立,则N = k + 1时,如果k为偶数,则k + 1为奇数,xk + 1的因数,只可能是奇数,而奇数减去奇数等于偶数,且k+1−x≤k,故轮到Bob的时候都是偶数。而根据我们的猜想假设N≤k的时候偶数的时候先手必胜,故此时无论Alice拿走什么,Bob都会处于必胜态,所以Alice处于必败态。如果kk为奇数,则k + 1为偶数,x可以是奇数也可以是偶数,若Alice减去一个奇数,那么k+1−x是一个小于等于k的奇数,此时Bob占有它,处于必败态,则Alice处于必胜态。综上所述,这个猜想是正确的。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/divisor-game