Maths Olympiad Prep

Library / /5 of 5

Number theory Difficulty 7.5 National olympiad, round 2 Prove it South Africa

Jacob and Laban take turns playing a game. Each of them starts with a list of square numbers 1,4,9,,202121, 4, 9, \dots, 2021^2, and there is a whiteboard in front of them with the number 00 on it. Jacob chooses a number x2x^2 from his list, removes it from his list, and replaces the number WW on the whiteboard with W+x2W + x^2. 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 44 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 KK such that Jacob can guarantee to get at least KK sheep by the end of the game, no matter how Laban plays?

Solution

Since n20(mod4)n^2 \equiv 0 \pmod{4} if and only if nn is even, and n21(mod4)n^2 \equiv 1 \pmod{4} if and only if nn is odd, we can simplify notation by replacing the even squares by 00 and the odd squares by 11, in each of the two lists. Thus Jacob and Laban each has a pool of 10101010 zeros and 10111011 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 20222022 ones between the two players, and 2022=4×505+22022 = 4 \times 505 + 2, Jacob is guaranteed to have at least 505505 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 506506 (or more) sheep after the game.

We now argue that if Laban plays intelligently, he can make sure that Jacob only get these 506506 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 4k4k-th one (where 1k5051 \le k \le 505), 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 4k4k-th one (for all 1k5051 \le k \le 505), 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 20202020-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 20202020 ones have been used, this offers no problem for Laban. Any zeros or ones played after the 20212021-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 4k4k-th one (for any 1k5051 \le k \le 505). 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 505505 produced by every fourth one. Hence, with this option where Jacob starts with a one, he is only guaranteed to earn 505505 sheep.

We conclude that Jacob can guarantee (by starting with a zero) to collect 506506 sheep for himself, but no more.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.