Jacob and Laban take turns playing a game. Each of them starts with the list of square numbers $1, 4, 9, \dots, 2021^2$, and there is a whiteboard in front of them with the number $0$ on it. Jacob chooses a number $x^2$ from his list, removes it from his list, and replaces the number $W$ on the whiteboard with $W + x^2$. Laban then does the same with a number from his list, and the repeat back and forth until both of them have no more numbers in their list. Now every time that the number on the whiteboard is divisible by $4$ after a player has taken his turn, Jacob gets a sheep. Jacob wants to have as many sheep as possible. What is the greatest number $K$ such that Jacob can guarantee to get at least $K$ sheep by the end of the game, no matter how Laban plays?
Problem
Source: South African Mathematics Olympiad 2021, Problem 6
Tags: game, combinatorics, number theory
11.08.2021 23:55
It seems to be $\boxed{K=506.}$ Replacing the square numbers by their resides mod $4$, each player starts with $1011$ ones and $1010$ noughts. The total on the whiteboard (in this trivially modified game) will end up at $2022$; so, since it is guaranteed to pass through the $505$ numbers $4,8,\ldots,2020$, the game will reward Jacob with at least $505$ sheep no matter what. By playing $0$ to start with, Jacob can also claim a sheep at the start, thus $K\ge 506.$ Now we show that Laban can prevent Jacob's reward climbing any higher by ensuring that the game never dwells on a multiple of $4$ total: If Jacob plays $0$ to start, Laban responds with $1$. Thereafter, whatever Jacob plays, Laban follows with the same value, so that it is always Jacob who brings the total to $0$ mod $4$, which is then changed immediately to $1$ mod $4$ by Laban. Laban will be unable to respond when Jacob plays his last $1$, but since the total at that point is $2022\ne 0\!\pmod{4}$ it does not matter. The reward is $506$ sheep. If Jacob plays $1$ to start, Laban responds with $0$. Then, up to move $m$ (say) when Laban is unable to respond to Jacob's final $0$, Laban mirrors Jacob as described previously. After move $m$, every play is a $1$, so we continue to move straight on past multiples of $4$ total. The reward is $505$ sheep.