Winning strategy writing a binary number

Question

A and B play by turns to write ones and zeros in a list, from left to right.The game ends when each has written 2013 numbers.When the game ends the sequence of numbers is seen as the expansion of a binary number.A wins if that number can be written as the sum of two perfect squares and B win otherwise.Who has the winning strategy and what is the winning strategy ?

Answer 1

Hint: one particular phrase in that paragraph stands out as being more complex than the rest....

Answer 2

Two helpful results:

1. If $n$ is the sum of two squares then $n\not\equiv 3\pmod 4$.
2. If $4n$ is the sum of two squares then $n$ is the sum of two squares.

(To see the second claim, note that $a^2+b^2\equiv 0\pmod 4$ is only possible with $a,b$ both even)

Lemma 1. If A ever picks $1$, B can force a win.

Proof. We show by induction on $k\in\mathbb N$ that if A picks $1$ in any of the last $k$ moves, B wins. Assume A's last move is $1$. If B then also picks $1$, the resulting number is $\equiv 3\pmod 4$ and B wins. This shows the claim for $k=1$. Assume the claim is true for $k$. Now assume A picks $1$ in his $(k+1)$ last move. Then B can reply with $1$. By induction hypothesis we can assume that the remaining $k$ moves by A are all $0$. If B also picks $0$ for the remaining $k$ moves, the resulting number is a power of $4$ times a number $\equiv 3\pmod 4$, hence not the sum of two squares and B wins. $_\square$

Lemma 2. If A never picks $1$, B can force a win.

Proof. Assume A always picks $0$. Then B can achieve that the resulting digit sequence is $0\ldots010101$, i.e. the resulting number is $21$ and not the sum of two squares. $_\square$

Corollary. B can force a win. $_\square$

In fact, we can formulate an explcit strategy for B: If the number so far is $\underbrace{0\ldots 0}_{4021}$ or $\underbrace{0\ldots 0}_{4021}10$ or $\underbrace{0\ldots0}_{4021}1010$, pick $1$. In all other cases do the same move A just did.