There are $2018$ players sitting around a round table. At the beginning of the game we arbitrarily deal all the cards from a deck of $K$ 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 neighbors. It is only allowed to choose a player whose each neighbor holds a nonzero number of cards. The game terminates when there is no such player. Determine the largest possible value of $K$ 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. Proposed by Peter Novotný, Slovakia
Problem
Source: Czech-Polish-Slovak Match 2018, Problem 3
Tags: combinatorics
Yaghi
17.07.2018 22:56
Quite a hard problem for a medium level contest,anyway,here's the solution I came up with in about 2 hours.
if we have $n$ people,then the answer is $n-1$.
Lemma:
Assume that for a certain position,the game is played infinitely many times.Then there is a position which is repeated after finite number of moves(a position is determined by the number of cards each person has).Assume that position $A_1$ is repeated in $A_k$ and person $i$ has been chosen $x_i$ times during $A_1,A_2,\dots A_k$;then $x_1=x_2=\dots x_n$.
Proof:
since in $A_k$,every person has the same number of cards as $A_1$,for all $i$,we should have $2x_i=x_{i-1}+x_{i+1}$.Conclusion follows from extremal principle.
Lemma:
if at some position two neighbors have no cards,then the process will be eventually terminated.
Proof:
Note that we can never choose these two people,so the conclusion follows from previous lemma.
Lemma:
if at some point,we have a block of people with cards of the form $(0,1,1,\dots ,1,0)$ then eventually we will have two neighbors among them both having no cards.In the other words,game will be eventually terminated by the second lemma.
Proof
We proceed by induction on the number of $1$'s.base cases are easy to check.Note that by the first lemma,at some position we should choose one of this people,which would result a smaller block of this form,reaching to the induction hypothesis.
to show that $n$ doesn't work,let the people have $0,2,1,1,\dots 1$ cards in this order and in each move,choose the person who has no cards.Obviously this results a position which is identical to the previous one by rotation.So the process can be done infinity many times.
to show that $n-1$ works,just note that in the initial position,there must be a block of the form $0,1,1,\dots ,1,0$.to show this,assume that $k$ people have no cards and call them $a_1,\dots a_k$.then there is a person between $a_i$ and $a_{i+1}$ who has at least two cards.(and any other person has at least on card) but this means that the number of cards is at least $n$ (equality when $k=1$) or the distribution is $0,1,1,\dots ,1$,but this position is also terminated by the third lemma,so the answer is $n-1$ and we are done.