For the question about the stone game
>>13742398, here are some things to know:
This kind of game is called an "impartial game".
You can label each position with either winning or losing.
However, when you SUM two games, meaning you take two separate games and play one of them on your turn, then it's not clear how to figure out the winning positions and losing positions just by knowing which ones are winning and which are losing in the "component" games; there seems to be some information missing.
For example, as noted ITT, (losing losing) is a losing position, because the only option is to go to (losing, winning) or (winning, losing), from which one can go to (losing, losing) again. So these three kinds of positions are clear for which they are.
But for (winning, winning), sometimes it's winning, and sometimes it's losing. How can we know?
This is where Sprague-Grundy values come in. To each position in an impartial game, we can assign a natural number (0-indexed). A position with a value of 0 is losing, while a position with a positive value is winning.
Knowing these values for the component games, how can we figure out the values for the new game? It's easy: If you have a position P = (P1, P2), then SG(P) = SG(P1) xor SG(P2), SG meaning "Sprague-Grundy value", and xor meaning bit-wise xor (which is fucking weird).
So what are the SG values for the 1-pile divisor Nim game above? If you have n = k*2^m stones, k being odd, then SG(n) = m. That's why the odd positions were losing. For the 2-pile game, they are the positions where the exponent of 2 is the same in both games, because that's the only way to xor two numbers to get zero.
