Maths Olympiad Prep

Library / /31 of 31

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Czech Republic

There are 20182018 players sitting around a round table. At the beginning of the game we arbitrarily deal all the cards from a deck of KK cards to the players (some players may receive no cards). In each turn we choose a player who draws one card from each of the two neighbours. It is only allowed to choose a player whose each neighbour holds a nonzero number of cards. The game terminates when there is no such player. Determine the largest possible value of KK such that, no matter how we deal the cards and how we choose the players, the game always terminates after a finite number of turns.
(Peter Novotný, Slovakia)

Solution

The answer is K=2017K = 2017.
For K=2018K = 2018, we deal 22 cards to one player, 00 cards to one of his neighbours and 11 card to everyone else. Then in each turn we choose the player with 00 cards:
112011112011 \dots 11 \overbrace{\underbrace{20}_{\sim}}^{\sim} 11 \dots \rightarrow \dots 11 \overbrace{\underbrace{20}_{\sim}}^{\sim} 11 \dots
After each turn, the configuration stays the same – there is one player with 22 cards, one of his neighbours with 00 cards and all the others with 11 card (the only change is that the positions of the players with 22 and 00 cards is shifted). Therefore we can make moves forever and the game never terminates.
Whenever K>2018K > 2018, we can play forever using the same strategy as for K=2018K = 2018. We simply deal the extra cards arbitrarily and ignore them during the game.
Now we will prove that for K=2017K = 2017 the game terminates no matter how we play. Let us call zeros the players with no cards and ones the players with exactly one card. The zeros split the other players into segments of various lengths. When two zeros sit next to each other, they form a segment with a length of 00. Also note that there is obviously at least one zero when K=2017K = 2017.

Lemma. There exists a segment containing no other players than ones (possibly with a length of 00).
Proof. If we add to each segment the zero which bounds it in the clock-wise direction, then the sum of the lengths of all the segments will be 20182018. There are only 20172017 cards, therefore at least one segment contains fewer cards than players, which is possible only when all the players of this segment, except for the bounding zero, are ones. \square
Let us consider the shortest segment among the ones containing no other players than ones; the lemma assures the existence of such a segment. If we choose a zero adjacent to this segment, we shorten it by 11 (or by 22 — in the special case when there is exactly one zero in the game):
0111100^11102011102^1110 \dots * \overbrace{0111\dots10\dots}^{\hat{0}11\dots10\dots} \rightarrow \dots * \overbrace{2011\dots10\dots}^{\hat{2}11\dots10\dots}
If we choose one of the ones inside of the shortest segment, we create two even shorter segments:
0111111^11001103010^1110 \dots 01\dots1 \overbrace{111}^{\hat{1}} 1\dots10\dots \rightarrow \dots 01\dots1 \overbrace{0301}^{\hat{0}11\dots10\dots} \rightarrow
The length of the shortest segment could decrease only finitely many times. From the moment when it stops decreasing we won't be able to choose any of the zeros bounding the shortest segment, nor any of the ones inside of it. This means that the game will continue on the other side of the table between the bounding zeros of the shortest segment. The neighbours of these two zeros won't be able to get any more cards, so we cannot choose them anymore. The neighbours of these neighbours will thereby be chosen at most finitely many times (at most the number of times equal to the number of cards of these neighbours), so after some time we won't be able to choose them. We can use this reasoning repeatedly. The part of the table where we still can choose players eventually decreases, which means that the game cannot last infinitely long.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.