There are players sitting around a round table. At the beginning of the game we arbitrarily deal all the cards from a deck of 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 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 .
For , we deal cards to one player, cards to one of his neighbours and card to everyone else. Then in each turn we choose the player with cards:
After each turn, the configuration stays the same – there is one player with cards, one of his neighbours with cards and all the others with card (the only change is that the positions of the players with and cards is shifted). Therefore we can make moves forever and the game never terminates.
Whenever , we can play forever using the same strategy as for . We simply deal the extra cards arbitrarily and ignore them during the game.
Now we will prove that for 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 . Also note that there is obviously at least one zero when .
Lemma. There exists a segment containing no other players than ones (possibly with a length of ).
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 . There are only 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.
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 (or by — in the special case when there is exactly one zero in the game):
If we choose one of the ones inside of the shortest segment, we create two even shorter segments:
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.