Let $n \ge 3$ be a fixed integer. A game is played by $n$ players sitting in a circle. Initially, each player draws three cards from a shuffled deck of $3n$ cards numbered $1, 2, \dots, 3n$. Then, on each turn, every player simultaneously passes the smallest-numbered card in their hand one place clockwise and the largest-numbered card in their hand one place counterclockwise, while keeping the middle card. Let $T_r$ denote the configuration after $r$ turns (so $T_0$ is the initial configuration). Show that $T_r$ is eventually periodic with period $n$, and find the smallest integer $m$ for which, regardless of the initial configuration, $T_m=T_{m+n}$. Proposed by Carl Schildkraut and Colin Tang
Problem
Source: ELMO 2019 Problem 3, 2019 ELMO Shortlist C4
Tags: Elmo, combinatorics, Combinatorial games
rmtf1111
19.06.2019 23:52
It is not hard to find an example to prove that $m\ge n-1.$ Call a card numbered $k$ small if $1\le k\le n,$ medium if $n+1\le k \le 2n$ and big otherwise. Proving that in $T_{n-1}$ each player has a small card suffices to prove the problem. Substitute positions for players. Consider a contiguous block of small cards, note that after each turn it will "move" one position clockwise and might expand with one or two positions anti-clockwise. We say that a contiguous block $A$ joins $B$ if the most clockwise position which contains cards of $A$ becomes adjacent with the most anti-clockwise position which contains cards of $B,$ if this procedure happens than we forget about the existence of $A.$ Note that if $A$ joins it does not mean that $B$ joins $A,$ also a block can join itself, in this case every postion will contain exactly one small card. Consider all contiguous blocks $P_1, P_2, \cdots P_t$ present during $T_0.$ Note that if all blocks join some other block till $T_{n-2},$ inclusively, then there will be a block which joined itself, which finishes the problem. So WLOG assume that $P_1$ did not join any other block. Suppose that in $T_0$ the most clockwise position which contains a card of $P_1$ is $u,$ then no position clocwise to $u$ within block $P_1$ will not contain more than one card during $T_1, T_2, \cdots T_{n-2}$(this claim is pretty intuitive and easy to see but requires some simple techincal details which I won't write out as I am lazy, but induction should be enough). Moreover, during $T_1, T_2 \cdots T_{n-2}$ the position $u$ will not contain more than $2$ cards(an easy induction is enough to show this), and so in $T_{n-2}$ each position from $u+1$ to $u+n-2$ will contain at most one card, and $u$ will contain at most $2$ cards, whereby $u+n-1$ will be free of small cards as $P_1$ did not join any block, and so it's easy to finish from here.
MelonGirl
20.06.2019 00:17
We show with induction that eventually, the $n$ smallest numbers will all be in different people's hands, ie. no person has two numbers from $1$ to $n.$ Trivial note is that each of the $n$ largest numbers are greater then all of the smallest or middle $n$ numbers, and any of the $n$ smallest numbers are smaller then all the middle or largest numbers.
Base case: Clearly, card number $1$ will always rotate clockwise every step.
Inductive step: Assume that the cards numberd $1$ to $k \leq n-1,$ are all in different people's hands. Then, from each step onwards, these $k$ cards will always rotate simultaneously clockwise. If card $k+1$ is the smallest card in someone's hands currently, then we are done.
Otherwise, card number $k+1$ will be in the same hand as another card $i \leq k.$ However, note that card $k+1$ can never move Counterclockwise, because by inductive hypothesis all the $k$ smallest cards are never in the same people's hands and rotate clockwise simultaneously. Thus, card $k+1$ will stay where it is, until a gap comes to it, and it is the smallest in that hand. This necessarily eventually happens, as $k \leq n-1.$ Then, card $k+1$ also rotates clockwise indefinitely as the other cards $1$ to $k.$
Thus eventually, the $n$ smallest numbers will each be in a different person's hand. Similarly, eventually, the $n$ largest numbers will also be in different people's hands. At this point, the $n$ smallest numbers will simply rotate clockwise one person, simultaneously each step, and similarly, the $n$ largest numbers will rotate simultaneously counterclockwise. And the $n$ middle numbers will just stay in the same person's card forever. This is clearly periodic with period $n.$
BlazingMuddy
20.06.2019 05:46
Might be similar to above but at least better interpretation.
The smallest such $m$ is $n-1$
Call a card low if the value written into it is at most $n$, and call it high if the value written to it is at most $2n+1$. We interpret the position of these cards as a $3 \times n$ table, where the smallest-numbered card in each player's hands are put in the top row and the biggest one are in the bottom row; each column represents the player's hand. Below is an example of such an interpretation for $n = 6$.
\begin{tabular}{|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 7 \\ \hline
11 & 13 & 10 & 9 & 6 & 8 \\ \hline
12 & 14 & 15 & 16 & 17 & 18 \\ \hline
\end{tabular}
To interpret the next configuration, the numbers in the top row are moved one step to the right (cyclically, so the rightmost number goes to the leftmost cell). Similarly, the numbers in the bottom row are moved one step to the left. Then, each column is adjusted accordingly to make the order of the cards correct; i.e. the smallest number on the column is moved to the top row and the biggest is moved to the bottom row.
To prove that $T_r$ is eventually periodic with period $n$ and that the smallest such $m$ is $n-1$, we will prove that:
(1). For any configuration $T_0$, the first row set of values in $T_{n-1}$ must be $\{1, 2, \ldots, n\}$ and similarly the bottom row's set of values must be $\{2n+1, 2n+2, \ldots, 3n\}$.
(2). There exists a configuration $T_0$ such that the above statement does not hold if $n-1$ is replaced by $n-2$.
(3). If at a configuration $T_r$ it holds that the first row contains $1$ to $n$ and the bottom row contains $2n + 1$ to $3n$, then all following configurations has that property and in fact $T_r = T_{r+n}$.
The third point is kinda obvious because if such configuration is reached, then to reach the next configuration, what we would do is simply rotating the top and bottom row accordingly (without any column adjustment). For the second point, using the label $L$ for low cards and $H$ for the high cards, below is one such configuration $T_0$ (example for $n = 6$).
\begin{tabular}{|c|c|c|c|c|c|}
\hline
L & L & L & L & L & \\ \hline
& H & & & L & \\ \hline
& H & H & H & H & H \\ \hline
\end{tabular}
Now we are left to prove (1).
For the sake of the proof, we will focus only on the low cards; very similar arguments would hold for the high cards. We re-interpret the movement as instead of the top row moving one step to the right, it does not move. Meanwhile, the middle row rotates one step to the left and the bottom row moves 2 steps to the left (again, cyclically). This means that the players are also moving one step to the left, but it does not really matter for this argument.
Next, call a cell in the top row a hole if it does not contain a low card; i.e. not labelled $L$. Also, since a low card can only go to the lower row by switching with another low card, we can consider each $L$ being not able to go down; i.e. it can only go up, as we don't distinguish between the low cards. Hence, a non-hole cell in the top row cannot become a hole in the next configuration. Also, note that a column with a hole cell cannot contain any label $L$. Call a hole filled if it becomes filled with a label $L$. Our aim is to prove that all holes are filled after $n - 1$ steps. Consider the following illustration.
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& L & L & L & L & \\ \hline
& & L & L & & \\ \hline
& & & L & & \\ \hline
\end{tabular}
Fix a hole in configuration $T_0$, and suppose for the sake of contradiction that it's not filled at $T_{n-1}$. Without loss of generality, assume that it is on the first column. Put a "magical barrier" between the first column and the last column. Since the hole is not fixed, there must be a label in $T_0$ in the middle or the bottom row that rotates to the left at least $n - 1$ steps. But since the first column cannot contain $L$, it must pass through the magical barrier at some configuration $T_s$ for some $1\leq s\leq n-1$, and this can only be caused by it jumping from the cell in the bottom row and second column to the last column. But this means that the cell in the middle row of second column contains the label $L$ in $T_{s-1}$, and this label fills a row at $T_s$. A contradiction!
Hence, every hole is filled at $T_{n-1}$, and we are done.
Kayak
20.06.2019 10:52
Hmm my solution looks significantly different from the solutions above; I wonder if it's completely wrong ?
I claim the answer is $m = n - 1$. Call a card low lavil if it's value is in the range $\{1, 2, \cdots, n \}$, mid lavil if it's value is in the range $\{n+1, \cdots, 2n \}$ and soumil if it's value is in the range $\{2n+1, \cdots, 3n \}$.
Numbering the players $P_0, P_1, \cdots, P_n$ clockwise, if $P_0, \cdots, P_{n-2}$ has a low lavil, a mid lavil and a soumi each, and $P_{n-1}$ has two low lavil, one mid lavil and $P_n$ has two soumil, one mid lavil card we have $m = n-1$.
If at $T_r$, each player has a low lavil, mid lavil and soumil card then $T_{n+r} = T_{r}$ (the low lavil cards cycle clockwise, soumil cards cycle anticlockwise and mid lavil cards don't move). Now we shall show $m \leq n-1$, i.e in $T_{n-1}$ each player gets a low lavil, mid lavil and a soumil card.
Lemma 1: Let $n \ge 3$ be a fixed integer. A game is played by $n$ players sitting in a circle. Each player draws an arbitrary number of cards (possibly zero) from a shuffled deck of $n$ indistinguishable cards. Number the players $P_0, \cdots, P_{n-1}$. Then, on each turn, if a player $P_i$ has cards $\{c_0, \cdots, c_k \}$, then he passes $j$-th card to $P_{i+j}$ for all $j \leq k$ (in particular: he keeps $c_0$ to himself, and if he has no card he does nothing) and every player does this simultaneously to every card.
Let $S_r$ denote the configuration after $r$ turns (so $S_0$ is the initial configuration). Then at $S_{n-1}$ each player would have exactly one card each.
Proof: Let $p_i = \frac{\text{Number of cards of i-th player at the beginning}}{n}$. Take the unit circle in the complex plane, put a petrol tank with capacity of going $2 \pi p_i$ units at $e^{\frac{2 \pi i}{n}}$. Then by the well known gas station on circular track puzzle (see eg https://brainstellar.com/puzzles/225) there's an index $j$ such that $\sum_{0 \leq i \leq k} p_{i+j} \leq \frac{k}{n}$ for all $k \leq n$, which in turn implies $P_j$ wouldn't take any cards from anyone ever in the game (why ?). So WLOG assume $j = 0$. Then by induction $P_k$ wouldn't accept any cards after $k$-th turn so we're done $\blacksquare$.
Lemma 2 For $m \geq n-1$, each player in $T_m$ gets exactly one low lavil card (and by symmetry, exactly one soumil card)
Proof: Consider this game:
Quote:
Let $n \ge 3$ be a fixed integer. A game is played by $n$ players sitting in a circle. Initially, each player draws atmost three cards from a shuffled deck of $n$ cards numbered $\{ 1, 2, \dots, n \}$, such that all cards are distributed among the players. Then, on each turn, every player simultaneously passes the smallest-numbered card (if it exists) in their hand one place clockwise, keeps the second-smallest card (if it exits) and the third-smallest (if it exists) in their hand one place counterclockwise, while keeping the middle card. Let $H_r$ denote the configuration after $r$ turns (so $H_0$ is the initial configuration)
.
Now, consider any valid $T_0$, and give a low lavil card to the $i$-th player in $H_0$ iff the $i$-th player in $T_0$ also have the low lavil card. Then by a very easy induction for any $k$, the $i$-th player in $H_k$ has a card iff the $i$-th playe in $T_k$ also has that low lavil card. Now, assume the players and card's are indistinguishable and the players are placed along the vertices of a regular $n$-gon in the unit circle. Then from the perspective of an observer sitting at the center of the regular n-gon rotating at an angular velocity of $ \frac{2\pi}{n} \text{rad/turn}$ clockwise, the game $H_i$ has the same rule as $S_i$ ! So we're done by Lemma-1 $\blacksquare$.
By symmetry, at $T_{n-1}$ each player has exactly one soumil card too, and since each player has exactly three cards, each player has exactly one mid lavil card too. Then we're done, since this has period exactly $n$.
nukelauncher
22.06.2019 22:20
I initially only solved part 1, but with about an hour left I got an insight to part 2, so the solutions to the 2 parts are not that related.
Number the players $1,2,\dots, n$ clockwise. Let the entropy of a configuration denote the sum of all players' highest cards minus the sum of all players' lowest cards. Let $h(i, j)$ denote the highest card of player $i$ during $T_j$, and define $l(i,j)$ analogously. Then, if $e(i)$ is the entropy of $T_i$, we have \[e(i)=\sum_{k=1}^n h(k,i)-l(k,i).\]Claim. The entropy is monotonically increasing.
Proof. It is obvious that $h(i,j) \leq h((i-1)\pmod{n}, j+1)$ since player $i$ at $T_j$ passes his highest card to player $i-1$ at $T_{j+1}$, thus at $T_{j+1}$, player $i-1$'s highest card is at least what he received from player $i$. Similarly we can show that $l(i,j)\geq l((i+1)\pmod{n}, j+1$. Then,
\begin{align*}
h(1,i)&\leq h(n,i+1), &l(1,i)&\geq l(2, i+1)\\
h(2,i)&\leq h(1,i+1), &l(2,i)&\geq l(3, i+1)\\
&\vdots&\vdots\\
h(n,i)&\leq h(n-1,i+1), &l(n,i)&\geq l(1, i+1).
\end{align*}Adding up all the inequalities in the first column and subtracting all the inequalities in the second column yields $e(i)\leq e(i+1)$, completing the proof.
Now, call a configuration stable if each player has one card each in $\{1,2,\dots, n\}$, $\{n+1,n+2,\dots, 2n\}$, and $\{2n+1,2n+2,\dots,3n\}$.
Claim. If a configuration is not stable, then the entropy must change after $n$ moves.
Proof. Assume not. Then the set of the players' highest and lowest cards remains the same after $n$ moves, meaning that every player has a card in between every low card and every high card. The only way for this to happen is for the original configuration to be stable.
Finally, it is clear that the entropy is bounded between $2n$ and $2n^2$, therefore eventually the entropy will become $2n^2$ and the configuration becomes stable, so $T_i$ is eventually periodic with period $n$.
Claim. The minimal $m$ so that $T_m=T_{m+n}$ is $m=n-1$.
Proof. Suppose that the minimal such $m\geq n$. Then, there is either a card $k\in \{1,2,\dots, 2n\}$ such that \[k=h(i,0)=h(i-1,1)=\dots=h(i+1,n-1)\]or a card $k\in\{n+1,n+2,\dots,3n\}$ such that \[k=l(i,0)=l(i-1,1)=\dots=l(i+1,n-1),\]else the configuration became stable before $T_n$.
The 2 cases are symmetric so WLOG assume there is a card $k\in \{1,2,\dots, 2n\}$ such that $k=h(i,0)=h(i-1,1)=\dots=h(i+1,n-1)$. This means that for each of $n$ steps, $k$ is larger than the 2 cards of its owner. As the small cards cycle in the opposite direction, none of these cards are duplicates. Therefore, $k$ is larger than $2n$ distinct cards, a contradiction to the fact that $k\in \{1,2,\dots, 2n\}$.
Finally we show a construction to show $m\geq n-1$. Simply take a stable configuration and swap the middle card of player 1 for the high card of player $n$. Since for $0\leq i\leq n-2$ at $T_i$ player $n-i$ has no cards in $\{2n+1,2n+2,\dots,3n\}$, then it takes at least $n-1$ steps for $T_i$ to become stable.
Therefore, we have shown $m\geq n-1$ and $m\not\geq n$, thus $\boxed{m=n-1}$.
illogical_21
24.06.2019 04:44
solution i submitted which is "missing the crucial claim and proof that at time $k$, each block will be $k$-tailed" but otherwise fine
The answer is $m=\boxed{n-1}$.
Let the cards numbered $1,2,\ldots,n$ be DUE cards and the cards numbered $2n+1,2n+2,\ldots,3n$ be HOANG cards.
First we show that $T_r$ is eventually periodic with period $n$.
Note that DUE cards will always be passed clockwise, unless more than one DUE card is held by the same person, in which case the smaller card will be passed clockwise. Note that this means that if the DUE cards $1,2,\ldots,k$ are with different people, they will never be together again.
Claim. Eventually, each person will have exactly one DUE card.
Proof. Let $1\le k\le n$ be the largest integer such that $1,2,\ldots,k$ are all being held by different people. If $k=n$, then we are done. Otherwise, consider the card $k+1$, which must must be in the hands of someone holding one of the cards $1,2,\ldots,k$ by the assumption. We show that eventually, cards $1,2,\ldots,k+1$ are with different people. If cards $1,2,\ldots,k+1$ are not with different people, then card $k+1$ must be can't be passed counterclockwise or clockwise, since it shares a hand with one of cards $1,2,\ldots,k$. Then it stays in place as cards $1,2,\ldots,k$ shift clockwise. Since $k<n$, eventually, none of cards $1,2,\ldots,k$ will be with card $k+1$, as desired. Hence, eventually, cards $1,2,\ldots,n$ are being held by different people, so we are done.
Similarly, eventually, each person will have exactly one HOANG card. At this point, every DUE card will always be passed clockwise, and every HOANG card will always be passed counterclockwise, so it is clear that the configuration is periodic with period $n$.
Now we show that $m=n-1$, that is, $T_{n-1}$ is the first configuration that guarantees each person has one DUE and HOANG card.
If a person has one DUE card, it will be passed clockwise. If a person has two DUE cards, one of them will be passed clockwise, and the other will stay. If a person has three DUE cards, one of them will be passed clockwise, another passed counterclockwise, and one will stay.
Then we can represent each configuration by labeling each person with the number of DUE cards they have, so let $a_k$ be the number of DUE cards person $k$ has, where the players are numbered $1,2,\ldots,n$ in clockwise order. Also let $a_{k+n}=a_{k}$ from now on.
In particular, in each turn, the following happens simultaneously, for each $1\le k\le n$:
If $a_k=1,2$, then $a_k$ decreases by $1$ and $a_{k+1}$ increases by $1$.
If $a_k=3$, then $a_k$ decreases by $2$ and $a_{k-1},a_{k+1}$ increase by $1$.
Let a block be a group of consecutive nonzero $a_k$ surrounded by zeroes, in particular, let $[i,j]$ denote the block of nonzero $a_i,a_{i+1},\ldots,a_{j}$ where $a_{i-1}=a_{j+1}=0$, and let $a_i$ be the left end and $a_j$ be the right end of block $[i,j]$. For example, possible blocks are boxed below
\[\ldots,0,0,\boxed{1,2,3,2},0,0,0,0,\boxed{3,3,2,3},0,0,\boxed{3,3,2,2,1},0,0,\ldots.\]After a turn, the blocks would become
\[\ldots,0,0,0,\boxed{3,2,2,1},0,0,\boxed{1,2,2,3,2,1,1,2,2,2,2,1,1},0,\ldots.\]If two blocks end up touching, we merge them into a larger block.
We can represent every configuration as a set of blocks, let $T_p$ be represented by distinct blocks $B_p(1),B_p(2),\ldots,B_p(q)$ where $B_p(k)=[x_p(k),y_p(k)]$ and $x_p(1)<x_p(2)<\cdots x_p(q)$.
Claim. Blocks remain contigous, in other words, zeros cannot appear in the middle of a block and divide it into two or more blocks.
Proof. First we show that all of the terms except for the leftmost term cannot become zero. Consider the $a_i=3$ in the block. They lose a total of $2$ when they give $1$ to each of their neighbors $a_{i-1},a_{i+1}$, so their value is at least $3-2=1$. Consider the $a_i=2$ in the block. They lose a total of $1$ when they give $1$ to their neighbor $a_{i+1}$, so their value is at least $2-1=1$. Consider the $a_i=1$ in the block that are not the leftmost term. They lose a total of $1$ when they give $1$ to their neighbor $a_{i+1}$, but also gain $1$ from $a_{i-1}$, so they retain their value of $1$. Then the block remains contigous, as no zeros can split it from the inside, so we are done.
Then we can associate every block $B_{t-1}(k)$ with a block $B_t(k')$ that it becomes. Additionally, if several blocks merge together, then they become the same block.
Now let the sum of a block $[i,j]$ be $a_i+\cdots+a_j$, and let the sum of block $B_t(k)$ be $S_t(k)$.
Claim. If a block $B_{t-1}(k)$ does not merge in turn $t$, it becomes $B_t(k')$, where $S_{t-1}(k)=S_t(k')$.
Proof. Since the block remains contigous, the sum of the numbers within the block is clearly invariant, as transfers only occur within the block, so we are done.
Claim. If a block $B_{t-1}(k)=[x_{t-1}(k),y_{t-1}(k)]$ does not merge in turn $t$, it becomes $B_t(k')=[x_t(k'),y_t(k')]$, where $y_t(k')=y_{t-1}(k)+1$ and $a_{y_t(k')}=1$.
Proof. Each term $a_i$ gives $1$ to its neighbor on the right $a_{i+1}$, so $a_{y_{t-1}(k)}$ gives $1$ to $a_{y_{t-1}(k)+1}$, and $a_{y_{t-1}(k)+2}=0$ since no merging occurs, so $y_t(k')=y_{t-1}(k)+1$. Since $a_{y_t(k')}$ only receives $1$, we must have $a_{y_t(k')}=1$, so we are done.
This means that after a turn, if a block does not merge, it appends a $1$ to its right end. Hence, if it does not merge for $t$ turns, there will be $t$ ones appended to the right end. However, this is only true when $t$ is at most the sum of the block, since that is the maximum number of ones that can exist in the block. At that point, the block consists only of ones. Call such a block a mrdue. Note that the behaviour of mrdues is to just shift every term one spot to the right in each turn, until they merge with another block.
Claim. If $B_{t-1}(i)$ and $B_{t-1}(j)$, where $i<j$, merge in turn $t$, then $B_{t-1}(j)$ cannot be a mrdue.
Proof. Suppose that $B_{t-1}(j)$ is a mrdue. Then $a_{x_{t-1}(j)}=0$ in turn $1$, since mrdues shift every term one spot to the right in a turn. The right end of $B_{t-1}(i)$ becomes $y_{t-1}(i)+1$ in turn $t$. However, $x_{t-1}(j)>y_{t-1}(i)+1$ since the blocks had not yet merged in turn $t-1$, so there is a $0$ in the middle of the merged block, meaning they did not merge, contradiction. Then $B_{t-1}(j)$ cannot be a mrdue, as desired.
Call a block a $k$-ending block if its rightmost $k$ terms are $1$, in particular, a mrdue with sum $S$ is a $S$-ending block. Rephrasing the previous observation, if a block does not merge for $t$ turns, the block becomes a $\min(S,t)$-ending clock, where $S$ is the sum of the block.
Claim. If blocks $B_{t-1}(i_1),B_{t-1}(i_2),\ldots,B_{t-1}(i_j)$, where $i_1<i_2<\ldots,i_j$, merge into $B_{t}(k')$, then $B_{t}(k')$ must be a $t$-ending block.
Proof. Since $B_{t-1}(i_j)$ must be a $t-1$-ending block that is not a mrdue, we must have $a_{x_{t-1}(i_j)}=a_{x_{t-1}(i_j-1)}=\cdots=a_{x_{t-1}(i_j-t+2)}=1$, and $a_{x_{t-1}(i_j-t+1)}\ne0$. Then in turn $t$, $B_{t-1}(i_j)$ appends another $1$ to its right end, making a total of $t$ ones, and now $B_{t}(k')$ is a $t$-ending block, as desired.
Finally, we put it all together.
Claim. At turn $n-1$, there is an $n-1$-ending block.
Proof. Eventually, the configuration becomes a single circular block, which means there must be some turn $t_e$ where the final merging occurs, and only a single $t_e$-ending block $B_{t_e}(1)$ with sum $n$ is left. Then it is clear that for $t_e\le t\le n$, the block $B_{t}(1)$ is a $t$-ending block, in particular, $B_{n-1}(1)$ is a $n-1$ ending block, as desired.
Since the sum of $B_{n-1}(1)$ is $n$, and there are $n-1$ ones in the block, the remaining term to the left of the appended ones must also be a $1$, and we have reached the single circular block. This guarantees that each player has a DUE card within $n-1$ turns, so it remains to show that $n-1$ is attainable. Indeed, consider the construction $a_1=1,a_2=1,\ldots,a_{n-2}=1,a_{n-1}=2,a_n=0$, which clearly works. In terms of cards, we can give card $k$ to person $k$ for $1\le k\le n-1$, and give card $n$ to person $n-1$.
Then turn $n-1$ is the earliest turn where each player is guaranteed to have a DUE card. With an analogous argument, turn $n-1$ is also the earliest turn where each player is guaranteed to have a HOANG card. Hence, turn $n-1$ is the earliest turn where the configurations become periodic, equivalently, $n-1$ is the smallest integer $m$ for which, regardless of the initial configuration, $T_m=T_{m+n}$.
Pluto04
08.07.2019 17:48
This is the solution I submitted during exam.Not sure if it is correct.
Let,$P_{i}$ denote $i^{th}$ person and let $i_{1}^{k}$ , $i_{2}^{k}$ and
$i_{3}^{k}$ denote the card numbers which $i_{th}$ person has after k turns
such that $i_{1}^{k}$ < $i_{2}^{k}$ < $i_{3}^{k}$ .
Now clearly after some k turns, (for 1≤i≤n)
$i_{1}^{k}$ will be a number in 1 to n.
$i_{2}^{k}$ will be a number in n+1 to 2n.
$i_{3}^{k}$ will be a number in 2n+1 to 3n.
Because after every turn the smallest number moves clockwise and hence, after
a point the smallest number that each person has is the smallest n numbers of first 3n natural numbers in some permutation. This means that $i_{1}^{k}$ will
be a number in 1 to n.
Using similar reasoning,the largest number will be a number in 2n+1 to 3n.
The remaining numbers are only n numbers which are in n+1 to 2n.
Now after this occurs configuration is reached , notice that the middle number of each person remains with the person , smallest numbers of n persons move in clockwise permutation and largest number of n persons move in anticlockwise
permutation in the circle.
So, exactly after n turns the same configuration is reached.
Hence,we have proved $T_{r}$ is eventually periodic with period n.
Now, we need to find smallest integer m such that $T_{m}$ = $T_{m+k}$
Which means that we need to find the smallest number of turns after
which the above configuration can be obtained.
Now clearly m=n because after every turn regardless of initial configuration,
one number in 1 to n will become the smallest number of a person which was before not the smallest number of any person and,
Similarly, one number in 2n+1 to 3n becomes the largest number of a person
which was before not the largest number of any person.
Hence,
The smallest integer m such that $T_{m}$ = $T_{m+n}$ is n.
CANBANKAN
13.01.2021 09:55
We will provide solution for part b) only. The answer is $m=n-1.$
I first show that it works. It suffices to show that after $n-1$ moves, each player only has one card from $\{1,\cdots,n\}$ and $\{2n+1,\cdots,3n\}.$ By symmetry, we will show each player only has one card from $\{1,\cdots,n\}$.
Let $a_i$ be the number of cards in $\{1,\cdots,n\}$ that player $i$ has. For convenience, $a_{n+i}=a_i$
Claim: There exist $i$ such that $\sum\limits_{j=i}^{i+k} (a_i-1)\ge 0$ for all $k$.
Proof. Note $\sum\limits_{j=1}^n (a_i-1)=0$.
We will construct $i$ with a process: start with $i=1$. Suppose $k$ is the smallest number such that $\sum\limits_{j=i}^{i+k} (a_i-1)< 0$. Then consider the same sum with $i+k+1$. If $i+k+1$ fails, say $\sum\limits_{j=i+k+1}^{i+k+l} (a_i-1)<0$, then $i$ also fails as $\sum\limits_{j=i}^{i+k+l} (a_i-1)=\sum\limits_{j=i}^{i+k} (a_i-1)+\sum\limits_{j=i+k+1}^{i+k+l} (a_i-1)< 0$. In this case, draw an arrow from $i$ to $i+k+1$.
Suppose we process the same $i$ again. Therefore, I have encountered a cycle. Suppose $i\rightarrow i+a_1\rightarrow i+a_2\rightarrow \cdots \rightarrow i+a_m \rightarrow i$. Let $a_0=0, a_{m+1}=kn$ for some integer $k$. Then we can see $\sum\limits_{x=0}\sum\limits_{j=i+a_x}^{i+a_{x+1}-1} (a_j-1) < 0$. However, the same sum is $\sum\limits_{j=1}^{kn} (a_i-1)=k\sum\limits_{j=1}^n (a_i-1)=0$, contradiction.
Therefore the graph formed by the arrows is a directed acyclic graph, this process would end and we would find a suitable $i$.
With this in mind, WLOG, this suitable $i$ is 1.
For convenience of writeup, we consider the same process, except for each player gives all cards to the next player on the same turn. We can also assume $a_n=0$. If $a_n>1, \sum\limits_{i=1}^{n-1} (a_i-1)<0$, and if $a_n=1$, we can start at $n$ instead. For now, we assume $a_1\ne 3$.
Main Claim: after $t$ turns, $a_1=a_2=\cdots=a_t=1$.
Proof of Main Claim: We proceed by induction on $t.$
Base Case: $t=1:$ consider the block of nonzero $a_i$'s starting at $1$. After one operation, $a_1=1$ because without shifting, $a_n$ would receive an element from the right, and if $a_{n-1}=3, \sum\limits_{i=1}^{n-2} (a_i-1)<0$, contradiction.
Inductive Step: Again, consider that block. We can see that $a_2,\cdots,a_t$ would be the result of $a_1,\cdots,a_{t-1}$, so $a_2=a_3=\cdots=a_t=1$.
Observation: $a_n>1, \sum\limits_{i=1}^{k} (a_i-1)\ge 0$ for all $k$.
Proof. We consider the behavior of blocks of elements. A few easy properties of blocks of nonzero $a_i$s:
(1) 0's don't appear in the middle of a block
(2) With the parallel operation, blocks cannot extend their boundaries to the left. Instead, they can only extend their boundaries to the right and merge with blocks to the right.
(3) If a block covers $[l,r]$, it (or whatever block it is merged to) would cover it forever.
With these properties in mind, we are ready to prove our observation. Suppose $a_n>1, \sum\limits_{i=1}^{k} (a_i-1)< 0$ for some minimal $k$. I only need to consider changes to $a_k$ and $a_1$. We will discuss $a_k$ first. Then on turn $t-1, \sum\limits_{i=1}^k (a_i-1)=0$. If $a_k>1, \sum\limits_{i=1}^{k-1} (a_i-1)<0$, which is a contradiction as I'm considering the earliest time when there is some $k$ that $ \sum\limits_{i=1}^{k} (a_i-1)< 0$ holds. If $a_k=0$, then $a_k$ cannot decrease. Therefore, $a_k=1,$ and on the next turn $a_k=0$. However, $k$ is covered by the interval at time $t-1$ but not covered by at time $t$, which is impossible by property (3).
Now we discuss $a_1.$ I just need to show it doesn't become $0$, for by inductive hypothesis, $a_1=1$. This is very straightforward; note $a_2>0$, or $a_1+a_2-2<0$.
Finally, we show that $a_1$ cannot increment. The only way that can happen is that the block to its left, which would contain the last block if I go around the circle from $a_1$ to $a_n$ and manage to increment $a_1$. This is impossible because if blocks $[l_k,r_k], [l_{k+1},r_{k+1}], \cdots, [l_e, r_e]$ manage to merge together and affect $a_1$, then $\sum\limits_{i=l_k}^n (a_i-1)>0$ because the sum of the numbers in the union of the blocks is an invariant and must be at least the length of its coverage. This would imply $\sum\limits_{i=1}^{l_k-1} (a_i-1)<0$, contradiction again. This completes the induction.
Setting $t=n-1$ yields $a_1=\cdots=a_{n-1}=1$ which means $a_n=1$.
If $a_1=3$ on first turn, after the first turn, we ask each player to give his card to the next player i.e. $a_{i+1}$ would have the cards $a_i$ has. Therefore, $m=n-1$ works.
Construction: let $a_1=2,a_2=\cdots=a_{n-1}=1, a_n=0$. We can easily show via induction that at turn $i\le n-2$, $a_1=\cdots=a_i=1, a_{i+1}=2, a_{i+2}=\cdots=a_{n-1}=1, a_n=0$. Therefore, at turn $n-2$ we are not done.
menpo
20.01.2021 13:41
Very simple solution with basic ideas Let's define sets $A, B, C$ in this way $A=\{3n, 3n-1,\ldots ,2n+1\},$ $B=\{2n, 2n-1,\ldots ,n+1\},$ $C=\{n, n-1,\ldots ,1\}.$ Note that each player has numbers from different sets if and only if $n$ becomes a period. Now let us prove that after $n-1$ moves, exactly this state always occurs (therefore $m=n-1$). We say that a player has a number $z$ or that he is equal to a number $z$ if he has exactly $z$ numbers from the set $A.$ First part: An example is the following: $2, 0, 1, 1, 1, ..., 1$ respectively, the numbers from the set $A$ for the players. Second part: Now we will prove that $n-1$ moves are always enough to eliminate all $0$ (therefore all equals $1$). Let $x(s, t)$ be the number of $A$ for the $s$-th player during the $t$-th move. Let the number be bad if it is 2 or 3, and good otherwise. We have the following lemmas: (prove it yourself, they are not that difficult) Lemma 1: $x(1, t) + x(2, t) + … + x(n, t) = n.$ (trivial) Lemma 2: If $x(s, t) = 0$, then $x(s-1, t-1)=0$ and $x(s, t-1)=$ good. Lemma 3: If $x(s, t)=$ bad, then $x(s, t-1)=$ bad OR $x(s+1, t-1) = 3$ (or just bad). WLOG assume that $x(n, n-1) = 0$ and $x(k, n-1) =$ bad. By Lemma 2 $x(n, n-1) = 0$ $x(n-1, n-2) = 0$ and $x(n, n-2)=$ good $\ldots$ $x(2, 1) = 0$ and $x(3, 1) =$ good $x(1, 0) = 0$ and $x(2, 0) =$ good By Lemma 3 $x(k, n-1) =$ bad $x(k, n-2)$ or $x(k+1, n-2) =$ bad $x(k, n-3)$ or $x(k+1, n-3)$ or $x(k+2, n-3) =$ bad $\ldots$ $x(k, 0)$ or $x(k+1, 0)$ or $\ldots$ or $x(k+n-1, 0)$ = bad Last part: Let $F(x(s,t))=t-s$ Consider the bad numbers initially $F(x(k,n-1))\ge0$ and finally $F(x(k,0))<0,$ and since it decreases in each step by 1 or 2, there exist a bad number $x(a,b)$ with $b-a = -1 \text{ or } -2,$ which is a contradiction by Lemma 2. We are done!
blackbluecar
07.02.2022 08:42
Define a Maxi to be a card $\geq 2n+1$. We claim that after $n+1$ moves, each player has a maxi. Indeed, label the players$P_1,P_2,...,P_n$ counterclockwise. Notice that rotating the picture so that $P_{i+1}$ is now $P_i$ is isomorphic to the original setup, thus we will consider behavior under this equivalent form. i) If $P_i$ has one maxi, they keep it. ii) If $P_i$ has two maxis, they give one to $P_{i-1}$ and keep the other one one iii) if $P_i$ has three maxis, they give one to $P_{i-1}$ and $P_{i-2}$ and keep the last one. Now, aftoc that after $n-1$ turns, some player does not have a maxi. This implies some player has two cards, let one of those cards be $C$. Notice that a player can never lose their card. Also, notice that if $C$ went around the whole circle to end up on or pass its original player. Thus, if the player that has no maxis is $P_k$ then it must be the case that $C$ skipped over $P_k$. But the only way that could happen is if there were three cards on $P_{k-1}$ including $C$. But, this would imply $P_k$ gains a card since both $P_{k}$ and $P_{k+1}$ would gain a card. Contradiction. Defining minis similarly gives a similar result. Thus, after $n-1$ moves, every player has a maxi and a mini. The behavior here becomes evident. Each player passes their maxi to their left and mini to their right. This creates a cycle of period $n$. To show $n$ is minimal, consider the following construction. $P_1,...,P_{n-2}$ has one maxi, $P_{n-1}$ has no maxis, and $P_n$ has two maxis.
IAmTheHazard
07.09.2023 15:39
extremely beautiful The answer is $m=n-1$. It will suffice to show the following claim. Claim: In $T_{n-1}$, the cards labeled $1,\ldots,n$ are all held by different players. (Equivalently, in $T_{n-1}$, the cards $2n+1,\ldots,3n$ are all held by different players.) Proof: We make the following modifications to the problem. Delete all the cards greater than $n$. Instead of the smallest-numbered card being passed clockwise, the smallest card is retained by each player. The second-smallest card is sent one clockwise, and the third-smallest is sent two clockwise. Instead of labeled cards, we use unlabeled balls that wear numbered hats. The hats represent the cards in the original sense, but we will track the movement of the balls. Finally, we modify the events of each turn in a way that clearly produces the same configuration as the original procedure. On each turn: If some player holds three balls, and the player directly clockwise from them holds no balls, then the first player passes their two highest balls one spot clockwise. Then every player sends the balls clockwise according to the rules mentioned above. Then, if a player had a ball at the very beginning of the turn that has not moved this turn, the hats are rearranged within each player's collection such that this ball is given the lowest numbered hat available. In particular, this ball does not move the next turn either. It is clear that once a ball stops moving, it cannot start moving again; in particular, once a player obtains a ball, they can never have no balls (this is true even without these modifications). On the other hand, if after exactly $i$ turns some ball has not stopped moving, it has clearly visited a contiguous subset of at least $i+1$ players. Therefore, if after $n-1$ turns there exists some ball $b$ which shares a player with a smaller-label ball (hence $b$ has not stopped moving), then $b$ has visited every player. On the other hand, if this happens then some player must not hold any balls: contradiction, since $b$ has visited them. $\blacksquare$ This claim implies that in $T_{n-1}$, each player holds a "small" card whose label is in $\{1,\ldots,n\}$, a "big" card whose label is in $\{2n+1,\ldots,3n\}$, and a "medium" card whose label is in $\{n+1,\ldots,2n\}$. Then in each successive turn, the small cards collectively rotate one player clockwise, the big cards collectively rotate one player counterclockwise, and the medium cards stay put, hence it is still true that each player still has one card of each type. Hence after $n$ turns, the small and large cards have rotated $n$ players clockwise and counterclockwise respectively, which means they are held by the same players as they were $n$ turns ago. Finally, we provide a counterexample that shows $m \geq n-1$. It suffices to exhibit some arrangement of the cards from $1$ to $n$ such that the cards are not all held by different players in $T_{n-2}$. If the players are labeled $1$ through $n$ in clockwise order, then giving player $1$ the cards labeled $1$ and $n$ and giving player $i$ the card labeled $i$ for $2 \leq i \leq n-1$ will work, since in $T_{n-2}$ player $n-2$ will hold cards $n-2$ and $n-1$. We are done. $\blacksquare$ Remark: This solution is mainly motivated by the fact that if each player held at most one "small" card, the conclusion would be easy, but in the actual problem there is the issue of cards being able to "jump" over holes—players without cards. However, it turns out that this is a non-issue (and intuitively this should be true since holes get "filled"), and the modifications we do to the problem make this extremely clear. The idea of introducing balls and hats is similar to the "ants on a stick" problem and this IMO problem IMO 2000/3 on fleas .
YaoAOPS
29.09.2023 05:23
Groupsolved with leo.euler, very nice problem and riddle. We use the following trick: if the cards at a position are $a < b < c$, then fix $a$, move $b$ one to the right, and move $c$ two the right. Label the hands $C_1, C_2, \dots, C_{n}$ cyclically and going clockwise. Claim: This doesn't hold for after the first $n - 2$ exchanges. Proof. Put $1, n$ in $C_1$, and $i$ in $C_i$ for $2 \le i \le n-1$. Then after $n-2$ moves, $n$ moves to $C_{n-1}$ as $1$ through $n - 1$ do not move. However, after another move, it follows that $n$ has moved to $C_n$ at which point it stops moving. $\blacksquare$ Claim: The cards $\{1, 2, \dots, n\}$ are all in different hands after $n-1$ moves. Proof. Color all these cards the same color and don't distinguish between them, as their internal order doesn't affect anything else. Ignore the remaining cards. Then whenever we have $2$ or $3$ cards in one hand, we spread them all out to the right. Whenever more than $1$ card are in the same hand, arbitrary fix one of them to never move under the operation. We can do this by relabelling to the smallest card in this hand as necessary. Call a hole a hand with none of these cards in it. Whenever a card ends up a hole, it then fills in the hole. Note that this generalizes to always filling a hole whenever a card would jump over it. Suppose there are $k$ holes initially and consider any one card. FTSOC suppose that it never falls in a hole, which means that it has made a full loop around. However, the other cards in a hole can fill at most $k - 1$ of the holes, forcing the card to fall in the remaining hole, contradiction. $\blacksquare$ Then, repeating a similar arguement, $\{2n + 1, \dots, 3n\}$ are also disjoint after the process. Thus, after $n - 1$ moves, each hand consists of one card from each set in the partition $A_1 = \{1, 2, \dots, n\}, A_2 = \{n+1, \dots, 2n\}, A_3 = \{2n+1, \dots, 3n\}$. Considering this operation, it then follows that cards in $A_1$ always move to the left, the cards in $A_2$ stay still, and the cards in $A_3$ move to the right. Thus, after another $n$ moves, all cards end up in the same starting position.
CT17
18.05.2024 22:15
Key claim: After $n-1$ turns, the cards $1$ through $n$ are held by distinct players. Proof: Imagine the cards $1$ through $n$ as indistinguishable dots distributed among $n$ positions around a circle. Each position starts with at most $3$ dots. On each turn, a position's first dot (if it exists) is sent clockwise, its second dot (if it exists) is fixed, and its third dot (if it exists) is sent counterclockwise. Now, compose each turn with a counterclockwise rotation by one position so that a position's first dot (if it exists) is fixed, its second dot (if it exists) is sent counterclockwise, and its third dot (if it exists) is sent two positions counterclockwise. Note that once a position has at least one dot, it is never empty. Now, consider any initially empty position $P$. We can imagine that each move, excess dots move $1$ or $2$ positions counterclockwise, and stop if they land in empty positions. Hence after $n-1$ moves, all initial excess dots must have landed in empty positions or crossed $P$. If $P$ is still empty, then since there are $n$ dots and only $n-1$ other positions, some dot must have crossed $P$. But $P$ must have been filled during the crossing, a contradiction as desired. By the claim (and symmetry), after $n$ moves cards $1$ through $n$ are held by distinct players and cards $2n+1$ through $3n$ are held by distinct players. It clearly follows that cards $n+1$ through $2n$ are also held by distinct players. But then each turn simply rotates the circle of small cards clockwise, rotates the circle of large cards counterclockwise, and fixes the circle of medium cards. Hence, the configuration is periodic with period $n$ starting from $T_{n-1}$, as desired. To see that $n-1$ is optimal, place cards $1$ through $n-1$ around the circle in counterclockwise order, and give card $n$ to the player holding card $1$. After $n-2$ turns, cards $n$ and $n-1$ are held by the same player, but they are held by different players when the configuration becomes periodic
KevinYang2.71
19.05.2024 04:04
Claim. After $n-1$ turns, everyone will have a card in $[n]:=\{1,\ldots,n\}$. Proof. Consider only $[n]$. Note that the numbers on the cards do not matter anymore. If a player has exactly $1$ card in $[n]$, he passes it clockwise. If he has exactly $2$ cards in $[n]$, he passes one clockwise and keeps the other. If he has exactly $3$ cards in $[n]$, he passes one clockwise, one counterclockwise, and keeps one. This is equivalent to every player keeping one card and passing his remaining cards counterclockwise by $1$ and $2$ if needed, since rotations do not change anything. If there is someone who does not have a card, a turn can be made. Suppose for the sake of contradiction someone has $\geq2$ cards after $n-1$ turns. Then one of those cards traveled $\geq n-1$ counterclockwise during the $n-1$ turns, so it traveled the whole circle. Thus everyone has a card, a contradiction. $n-1$ turns are necessary since we can give everyone but player $A$ a card, and give the player immediately counterclockwise to $A$ another card. $\square$ Note that after everyone has a card in $[n]$, they will always pass these cards clockwise so this status is kept. Similarly, after $n-1$ turns, everyone will have a card in $\{2n+1,\ldots,3n\}$. They will pass these cards counterclockwise. It follows that the remaining cards $n+1,\ldots,2n$ will also be distributed to distinct players. These cards are always kept. Thus the game is periodic with period $n$ and $\boxed{m=n-1}$. $\square$