Divisor Game

Problem

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player’s turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n and n % x == 0.
• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

Constraints

• 1 <= n <= 1000

Solution

The problem Divisor Game can be solved using a dynamic programming. For a game where there is a number n on the chalkboard, let F(n) = true or false where F(n) is true when first person starting wins the game and false when first person starting loses the game. Then the problem becomes equivalent to checking if there are any x that satisfies F(n-x) = false. Moreover, after some observation, we can prove that Alice wins when n is even and loses when n is odd using a mathematical induction. First, it is obvious that F(1) is false, F(2) is true. Next, let’s assume F(k) = (k % 2 == 0) for all k where k < n and n is an odd number. Then, F(n) = !F(n-x) = false since all divisors for n are odd, which makes n-x even. Also, F(n+1) = !F(n) = true because when both players play optimally, Alice will choose 1, which will always make Bob lose. In conclusion, we have shown that F(n) = (n % 2 == 0) holds true for all integer n.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool divisorGame(int n) { return !(n & 1); }
};