, 2019

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Netherlands

Thomas and Nils are playing a game. They have a number of cards, numbered $1$ , $2$ , $3$ , et cetera. At the start, all cards are lying face up on the table. They take alternate turns. The person whose turn it is, chooses a card that is still lying on the table and decides to either keep the card himself or to give it to the other player. When all cards are gone, each of them calculates the sum of the numbers on his own cards. If the difference between these two outcomes is divisible by $3$ , then Thomas wins. If not, then Nils wins.

a. Suppose they are playing with $2018$ cards (numbered from $1$ to $2018$ ) and that Thomas starts. Prove that Nils can play in such a way that he will win the game with certainty.

b. Suppose they are playing with $2020$ cards (numbered from $1$ to $2020$ ) and that Nils starts. Which of the two players can play in such a way that he wins with certainty?

Solution

a.
Thomas and Nils both make $1009$ moves and Nils makes the last move. Nils can make sure that the last card on the table contains a number that is not divisible by $3$ . Indeed, he could start taking cards with numbers that are divisible by $3$ , until all these cards are gone. Because there are only $672$ such cards, he has enough turns to achieve that.

We now consider the situation before the last move of Nils. Let $k$ be the number on the last card, and let the sums of the numbers of Thomas and Nils at that very moment be $a$ and $b$ . Nils has two options. If he gives away the last card, the difference between the outcomes becomes $(a+k) - b$ , and if he keeps the card, the difference becomes $a - (b+k)$ . Nils is able to win, unless both numbers are divisible by $3$ . But in that case $(a+k-b) - (a-b-k) = 2k$ would also be divisible by $3$ . Because $k$ is not divisible by $3$ , the number $2k$ is also not divisible by $3$ and hence Nils can win with certainty.

b.
Nils can win. We distinguish three types of cards, depending on the number on the card: type $1$ (the number has remainder $1$ when dividing by $3$ ), type $2$ (the number has remainder $2$ when dividing by $3$ ), and type $3$ (the number is divisible by $3$ ). Because $2019 = 3 \cdot 673$ and the card $2020$ is of type $1$ , there are $674$ cards of type $1$ , $673$ cards of type $2$ , and $673$ cards of type $3$ .

In order to win, Nils chooses a card of type $3$ in his first turn (and gives it to Thomas). Then there are $674$ cards of type $1$ left, $673$ of type $2$ , and $672$ of type $3$ . In the next turns he responds to Thomas's move in the following way (as long as he is able to).

(i) If Thomas chooses a card of type $1$ , then Nils chooses a card of type $2$ and gives it to the same person that got Thomas's card.

(ii) If Thomas chooses a card of type $2$ , then Nils chooses a card of type $1$ and gives it to the same person that got Thomas's card.

(iii) If Thomas chooses a card of type $3$ , then Nils does the same (and gives the card to Thomas).

As long as Nils keeps this up, the sum of each player's cards is divisible by $3$ after his turn (because a number of type $1$ and a number of type $2$ add up to a number which is divisible by $3$ ).

Because the number of cards of type $3$ is always even after Nils's turn, Nils can always execute his planned move in case (iii). Because the number of cards of type $1$ is always $1$ greater than that of type $2$ after Nils's turn, he can also always execute his planned move in case (ii). Only at the moment when all cards of type $2$ are gone and Thomas takes the last card of type $1$ (case (i)), Nils cannot execute his planned move. However, in that case Nils cannot lose anymore. Indeed, after Thomas's turn the sum of the cards of one player is still divisible by $3$ , but the sum of the cards of the other player is not divisible by $3$ anymore. Because there are only cards of type $3$ left now, this will stay the same until all cards are gone. At the end, the difference between the sums of both players is not divisible by $3$ and Nils wins.

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.