Subtraction of Squares (3/3 – 3/16)
There are \(4n\) cards on the table with the integers \(1\) through \(4n\). Alice and Bob are playing a game where starting from Alice, each player chooses a card, adds it to the sum (which starts at \(0\)). If the sum cannot be written as the difference of two square integers (i.e. \(a^2-b^2\) for some \(a, b \in \mathbb{Z}\)), the player that put the final card loses.
For which values of \(n\) does Alice win?
Solution
First, we show that \(n\) cannot be written as difference of squares if and only if \(n \equiv 2 \pmod{4}\).
Noting that \(n^2 \equiv 0, 1 \pmod{4}\), we see that \(a^2 \ – \ b^2 \neq 2 \pmod{4}\).
If \(n \equiv 0 \pmod{4}\), \(n = 4k\) so \(n = (k+1)^2 \ – \ (k-1)^2\).
If \(n \equiv 1 \pmod{2}\), \(n = 2k + 1\) so \(n = (k+1)^2 \ – \ k^2\).
So, we can treat the \(4n\) cards as \(n\) cards of \(0,1,2,3\).
We claim that if \(n\) is odd, Alice wins and Bob wins otherwise.
Case 1: \(n\) is odd
Alice starts by taking \(0\) and if Bob takes \(1\), Alice takes \(3\) and vice versa. If Bob takes \(0\), Alice does as well. Eventually Bob will have to take a \(2\) and lose.
Case 2: \(n\) is even
Bob uses the same strategy from above. If Alice takes \(0\), Bob takes \(0\). If Alice takes \(1, 3\), then Bob takes \(3, 1\) respectively. Eventually Alice will have to take a \(2\) and lose.