Player $A$ and $B$ play a game: There are two stacks of coins, first stack has $a=12$ coins, second - has $b=8$ coins. Each player choose a stack and remove $d$ coins, if choose first stack $d|a$, otherwise $d|b.$ Player win if other player can't move. Which player has a winning strategy?
How change the answer if $a=20,b=28$?
I know answer by trials if $a=5,b=3$ - $B$ has winning strategy: this player take one coin from this stack, which was choosed by $A$ at last move, if it is possible. If it isn't possible, it means that $A$ get last coin on the stack.
I have problem to see a general pattern. I thought that in situation that $a=12,b=8$ $B$ get not one coin, but $gcd(12,8)=4$ coins by analogy to situation described above; I don't see at moment any reason.
I was able to find the solution, though I cannot explain how unless you are familiar with combinatorial game theory.
A position $(a,b)$ is either a win for the first or second player. If exactly one of $a$ or $b$ is zero, then the position is a first player win, and the winning move consists of reducing the nonzero stack to zero.
Otherwise, let $v(a)$ be the largest power of two dividing into $a$. For example, $v(20)=4, v(120)=8, v(16)=16, v(\text{any odd number})=1$.
When $(a,b)=(12,8)$, then $v(a)=4$ and $v(b)=8$, so this position is a win for the first player. A winning move is to decrease $8$ by $4$, resulting in the position $(8,8)$.
When $(a,b)=(20,28)$, then $v(a)=4$ and $v(b)=4$, so this position is a loss for the first player. This means every move for the first player has a winning response: for example, if the first player removes $4$ from the first stack, leaving $(16,28)$, then the second player would respond by removing $v(28)=4$ from the $16$ stack, leaving $(12,28)$.
To prove the Theorem, you just need to show two things. Call a position equalized if $v(a)=v(b)$.
If a position is not equalized, then performing the move described above equalizes it.
If a position is equalized, then any move will leave it unequalized.
I leave these proofs to the reader.
As to how I found this strategy; the two stack game is the sum of two one-stack games. You can compute the Grundy values of a one-stack game recursively by making a table, and for each entry letting the value be the mex of the values of that number minus its divisors. After doing that I saw a pattern and proved it. I do not now how I would have seen the pattern without familiarity with the italicized concepts.