I saw an interesting question in Dynamic Programming (DP) section on Leetcode webpage.
Given an integer $n \ge 1$, A and B play the following game.
A picks a number $0<k<n$, such that $k | n$ ($k$ divides $n$). Then $k$ is subtracted from $n$ and player B plays the same game but with $n-k$ instead of $n$. This goes back and forth until a player is unable to move (due to no valid moves), who loses the game.
The question was to write a program that given $n$, we should determine if $A$ is guaranteed a win or not, by appropriately choosing the factors.
As an example, if $n=10$,
A can pick $1$ or $5$. A picks $5$, therefore $10-5 = 5$
B picks $1$, therefore $5-1 = 4$
A can pick $1$ or $2$. A picks $1$, therefore $4-1 = 3$
B picks $1$, therefore $3- 1 = 2$
A picks $1$, therefore $2 - 1 = 1$
B cannot pick any integer in $[0,1]$. Thus A wins. Note that if $A$ had picked $2$ instead, he would have lost as long as $B$ played rationally.
While I coded this using a DP and got the correct result, I observed an unusual pattern in the solutions. I observed that if $n$ is odd, B was guaranteed to win and if even, as illustrated, $A$ was guaranteed to win, as long as both players play rationally. Unfortunately I could not prove it. Out of curiosity, I replaced my entire DP code with just the odd/even check. It passed all test cases and was accepted !!
Given the factors of $n$ playing a crucial role here, I think it may have something to do with some number theoretic result like Gauss Theorem ($\sum_{d|n}\phi(d) = n$). But I am unable to write the proof concretely. I appreciate any hints in this regard.
This can be more concisely proved by induction, but the here is a more instructive reasoning.
If Alice is given an even number $n$, then she will take $k=1$, and return $n-1$ to Bob. Now either Bob was given $n-1=1$, for which he already lost, or he had to take $k|n-1$ which is odd, therefore he will return $n-k$ which is even to Alice. So the numbers they get will alternate between even and odd, and eventually Bob will get $1$ as he is the one that always gets an odd number. (Note that Alice can win quicker by picking the maximal odd proper divisor $k$ of $n$ at each turn, but she can always pick $1$ to guarantee a win.)
On the other hand, if Alice was given an odd number $n$, then either she has already lost due to $n=1$ or she will have to return an even number to Bob as shown above, and then Bob will perform the above strategy to win.