Divisor Game

• Create a boolean DP array dp of size n + 1, initialized to false.
• Loop i from 2 to n.
• Inside this loop, loop x from 1 to i-1.
• If i is divisible by x, check the value of dp[i - x].
• If dp[i - x] is false, it means we found a move to a losing position for the opponent. Set dp[i] = true and break the inner loop.
• After the loops complete, return dp[n].

We can solve this game theory problem using a bottom-up dynamic programming approach. The state of the game is defined by the current number n on the chalkboard.

Let dp[i] be a boolean value indicating if the current player can win starting with the number i.

• dp[i] = true means the current player can win.
• dp[i] = false means the current player will lose if the opponent plays optimally.

The goal is to compute dp[n].

• Base Case: For n = 1, there are no valid moves (0 < x < 1 is impossible). So, the player whose turn it is loses. dp[1] = false.

• Transitions: For any number i > 1, the current player wins if they can make a move to a number i - x (where x is a proper divisor of i) from which the other player loses. In other words, dp[i] is true if there exists a divisor x of i such that dp[i - x] is false.

We can build up the dp table from i = 2 to n.

1class Solution {2    public boolean divisorGame(int n) {3        boolean[] dp = new boolean[n + 1];4        // In Java, boolean arrays are initialized to false.5        // So dp[1] is already false.6        7        for (int i = 2; i <= n; i++) {8            for (int x = 1; x < i; x++) {9                if (i % x == 0) {10                    // Check if moving to i-x is a winning move.11                    // A move is winning if the opponent is left in a losing state.12                    // A losing state for the opponent is one where dp[state] is false.13                    if (!dp[i - x]) {14                        dp[i] = true;15                        break; // Found a winning move, no need to check further for this i.16                    }17                }18            }19        }20        return dp[n];21    }22}

• Check if the input number n is even.
• If n is even, return true.
• If n is odd, return false.
• This can be implemented with a single expression: n % 2 == 0.

By analyzing the game, we can deduce a simple mathematical rule that determines the winner.

Let's prove by induction that the first player (Alice) wins if n is even and loses if n is odd.

• Base Cases:

  • n = 1: n is odd. Alice has no moves and loses. The rule holds.
  • n = 2: n is even. Alice chooses x=1, n becomes 1. Bob receives 1 and loses. Alice wins. The rule holds.

• Inductive Hypothesis: Assume for all integers k < n, the current player wins if k is even and loses if k is odd.

• Inductive Step:

  • Case 1: n is odd. Alice must choose a divisor x of n. Since n is odd, all of its divisors x must also be odd. The new number becomes n - x. The difference between two odd numbers (n and x) is always an even number. So, Alice must pass an even number to Bob. By the inductive hypothesis, Bob receives an even number and wins. Since every move Alice makes leads to a winning position for Bob, Alice will lose if n is odd.
  • Case 2: n is even. Alice can simply choose x = 1 (which is always a divisor for n > 1). The new number becomes n - 1. Since n is even, n - 1 is odd. Alice can pass an odd number to Bob. By the inductive hypothesis, Bob receives an odd number and loses. Since Alice can make a move that forces Bob into a losing position, Alice will win if n is even.

Thus, the proof is complete. Alice wins if and only if n is even.

1class Solution {2    public boolean divisorGame(int n) {3        return n % 2 == 0;4    }5}