Jacob and Laban take turns playing a game. Each of them starts with a list of square numbers , and there is a whiteboard in front of them with the number on it. Jacob chooses a number from his list, removes it from his list, and replaces the number on the whiteboard with . Laban then does the same with a number from his list, and they 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 after a player has taken their turn, Jacob gets a sheep. Jacob wants to have as many sheep as possible by the end of the game, whereas Laban wants Jacob to have as few sheep as possible. What is the greatest number such that Jacob can guarantee to get at least sheep by the end of the game, no matter how Laban plays?
Solution
Since if and only if is even, and if and only if is odd, we can simplify notation by replacing the even squares by and the odd squares by , in each of the two lists. Thus Jacob and Laban each has a pool of zeros and ones to choose from when the game starts.
Our first observation is that, no matter in which order they write down their ones and zeros on the board, after every fourth one, Jacob will earn another sheep. Since there are in total ones between the two players, and , Jacob is guaranteed to have at least sheep after the game. But since Jacob has the privilege of playing the first move, he can start with one of his zeros, which will secure a further sheep for himself, leaving him with a total of (or more) sheep after the game.
We now argue that if Laban plays intelligently, he can make sure that Jacob only get these sheep, and nothing more. The secret for him is to make sure that no zeros are played (by anybody) immediately after every fourth one. Such zeros would add more sheep to Jacob's collection. So, immediately after every -th one (where ), another one should follow. Laban can easily achieve this by writing down a one after the zero with which Jacob has started the game, and after that simply copying each move of Jacob. This will ensure that Jacob must write down every -th one (for all ), and Laban then follows with another one immediately after each of these ones, achieving his goal.
By following this rule, Laban will not run out of zeros or ones before the -th one has been used. After the first two moves (a zero by Jacob and a one by Laban), Laban has more zeros than Jacob, and one one less than Jacob in his pool, but since there are two spare ones left after ones have been used, this offers no problem for Laban. Any zeros or ones played after the -th one will not contribute to a sum divisible by four, hence no further sheep for Jacob.
There is, of course, also the possibility that Jacob decides (for whatever reason) to start with a one, and not a zero. If this is the case, then Laban simply copies each move by Jacob right from the start, except the second one played by Jacob (which will be the third one of the game). After this one, Laban should proceed with a zero (if there are any zeros left in his list), and then continue to copy each move of Jacob after that. In doing so, no zero will be played directly after the -th one (for any ). If there are no zeros left in Laban's list after the third one of the game, then there will also be no zeros left in Jacob's list. So Laban simply continues with the ones from his list and Jacob cannot earn any more sheep than the guaranteed produced by every fourth one. Hence, with this option where Jacob starts with a one, he is only guaranteed to earn sheep.
We conclude that Jacob can guarantee (by starting with a zero) to collect sheep for himself, but no more.