Let $n\ge 3$ be an integer. Two players, Ana and Beto, play the following game. Ana tags the vertices of a regular $n$- gon with the numbers from $1$ to $n$, in any order she wants. Every vertex must be tagged with a different number. Then, we place a turkey in each of the $n$ vertices. These turkeys are trained for the following. If Beto whistles, each turkey moves to the adjacent vertex with greater tag. If Beto claps, each turkey moves to the adjacent vertex with lower tag. Beto wins if, after some number of whistles and claps, he gets to move all the turkeys to the same vertex. Ana wins if she can tag the vertices so that Beto can't do this. For each $n\ge 3$, determine which player has a winning strategy. Proposed by Victor and IsaĆas de la Fuente
Problem
Source: Mexico National Olympiad 2020 P3
Tags: combinatorics, Circular array, vector
12.11.2020 03:48
I think $B$ can win if $n$ is an odd prime. Number the vertices clockwise,$v_1,v_2,...,v_n$ and let $v_i=v_j$ if $i \equiv j (mod n)$ for simplicity,after $A$'s move there are two kind of vertices: whose left neighbour is biger $L$ and whose right neighbour is biger $R$ (there is always at least one of every kind,just look at the neighbours of $1$ or $n$). If $n$ is even $A$ can assign the number $i$ to $v_i$,it follows that an odd number has even neighbours and viceversa,so the turkeys always change the parity of the number they are after $B$'s move, at the beggining there is at least one turkey in an odd position and one in an even position so these turkeys cannot stay in the same vertex and $A$ wins. If $n$ is odd and $n=kd$ for some $k, d>1$ then $A$ can make the groups $G_j={(j-1)d+1,...,jd}$ for $j=1,2,...,k$ and then distribute the elements of the group $G_r$ among the $k$ vertices with index congruent to $r (mod d)$, it is easy to see that $v_i$ and $v_{i+d}$ are of the same kind for all $i$,so the turkeys that are initially in $v_1$ and $v_{d+1}$ are always at distance $d$ so they never end in the same vertex and $A$ wins. If $n$ is an odd prime, it suffices to prove that every $2$ turkeys can end in the same vertex after some $B$'s moves. So look at two turkeys $S$ and $T$ and the even lenght arc they determine, $B$ performs the move that "approaches" $S$ to the position of $T$ along the even arc,if the vertex of $T$ is of the same kind of the vertex of $S$ the distance between $S$ and $T$ "$q$" remains the same, otherwise decrease by $2$, $B$ performs this move until we decrease the distance between $S$ and $T$ this will eventually happen since there exist a pair of vertices $v_p,v_{p+q}$ such that $v_p$ and $v_{p+q}$ are not of the same kind (suppose the contrary,then the vertices $v_{1+iq}$ for $i=0,...,n-1$ are of the same kind, but since ${0,q,...,(n-1)q}$ is a residue set $modn$ implies that all vertices are of the same kind, contradiction), then we can always decrease the even distance between $S$ and $T$ by $2$ so eventually they end up in the same vertex.
10.03.2021 06:46
Great problem. Here's my write-up: The answer is that Beto wins if $n$ is an odd prime, and otherwise Ana wins. If $n$ is even, Ana wins no matter what the tagging is, because by coloring the vertices of the $n$-gon in alternating colors, we find that the number of turkeys on one color always equals the number of turkeys of the other color. Therefore, we will assume $n$ is odd in what follows. Claim: For Beto to win, it is necessary and sufficient for Beto to be able to merge any two given turkeys. Proof. Clear. $\blacksquare$ Given two turkeys with odd $n$, there is a notion of even distance $d$ between them (by drawing the arc of even length). Hence one of left or right turkey. Note that: There is always a choice of move that moves the right turkey counterclockwise; hence it cannot decrease the even distance. We call this a safe move. Beto could try to decrease the even distance by repeatedly applying safe moves. If at any point one of the safe moves causes the left turkey to move clockwise (rather than counterclockwise), the even distance will decrease. If he is always able to do this, for any $d > 0$, he can eventually merge the turkeys. On the other hand, suppose there is an even distance $d$ for which safe moves do not ever decrease the distance. Then both turkeys will traverse the entire circle. With that notation, let's work through both situations. In what follows, the vertices are labeled $A_0$, $A_1$, \dots, $A_{n-1}$ in counterclockwise order, indices modulo $n$. Proof that Beto wins whenever $n$ is prime: Suppose for contradiction that there is an even distance $d$ such that Beto cannot get two turkeys of even distance $d$ closer. Consider any two vertices, say $A_0$ and $A_d$ which are $d$ apart. WLOG, suppose that clapping is a safe move (in other words, $A_{n-1} > A_1$). Then the clap makes the other turkey move away, meaning that $A_{d-1} > A_{d+1}$. This situation is illustrated for $d=4$ below, with green arrows marking the clap direction. [asy][asy] picture turkey; pen turkeyborder = black+1.2; pair[] A = new pair[11]; for (int i=0; i<=10; ++i) { A[i] = 5*dir(360*i/11); } picture leg; pen turkeyleg = rgb("cc3300") + 1.2; filldraw(turkey, scale(0.7)*unitcircle, rgb("cc0000"), turkeyborder); draw(leg, (0.5*dir(-70))--(1.6*dir(-70)), turkeyleg); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-95)), turkeyleg); draw(leg, (1.3*dir(-70))--(1.3*dir(-70)+0.3*dir(-50)), turkeyleg); add(turkey, leg); add(turkey, reflect(dir(-90), dir(90))*leg); filldraw(turkey, (1,0)--(-1,0)..(0,-1)..cycle, rgb("604020"), turkeyborder); // body of turkey draw(turkey, (0.1,-0.4)..(-0.2,-0.35)..(-0.6,-0.2), turkeyborder); // part of wing draw(turkey, (0.1,-0.8)..(-0.2,-0.7)..(-0.6,-0.2), turkeyborder); // part of wing filldraw(turkey, (1.2,0.3)--(1.2,0)--(1.7,0.15)--cycle, yellow, turkeyborder); // beak of turkey filldraw(turkey, circle((0.7,0.3), 0.6), rgb("e67300"), turkeyborder); // turkey head fill(turkey, ellipse((1.05,0.45), 0.08, 0.12), black); fill(turkey, ellipse((1.07,0.49), 0.02, 0.03), white); draw(turkey, (1.6,0.5)--(1.8,0.7)..(2.0,0.75)..(2.4,1.2)..(1.8,1.5)..(1.2,1.2)..(1.6,0.7)--cycle ); label(turkey, scale(0.7)*"\textsf{gobble}", (1.8,1.1), fontsize(9pt)); add(shift(1.4*A[0])*rotate(-90)*turkey); add(shift(1.4*A[4])*rotate(40)*turkey); size(9cm); draw(scale(5)*unitcircle, grey); dotfactor *= 2; draw(A[0]--A[4], blue); draw(A[4]--A[8], lightblue+dashed); draw(arc(origin, A[0], A[1]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4)); draw(arc(origin, A[4], A[5]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4)); draw(arc(origin, A[8], A[9]), deepgreen+1.8, EndArrow(TeXHead), Margin(0,4)); draw(A[10]--A[1], red, EndArrow(TeXHead), Margins); draw(A[3]--A[5], red, EndArrow(TeXHead), Margins); label(rotate(90)*"bigger than", A[10]--A[1], dir(180), red); for (int i=0; i<=10; ++i) { dot(A[i]); } [/asy][/asy] Now imagine the turkeys are situated at $A_d$ and $A_{2d}$. We have seen that clapping is the safe move for $A_d$; hence clapping is the safe move for $A_{2d}$ as well. Repeating this argument, and noting that $d < n$ means $\gcd(d,n) = 1$, we find that clapping is the safe move at every vertex. And that means we have the inequality chain \[ A_{n-1} > A_1 > A_3 > A_5 > \dots \]but this chain is cyclic and we get a contradiction. Proof that Beto loses whenever $n$ is composite: On the other hand if $n$ is an odd composite number, let $p$ be the smallest prime divisor of $n$, and focus on $d = 2 \cdot \frac np$. Then label $A_1$, $A_3$, \dots, $A_{n-2}$, $A_n$, $A_2$, \dots, $A_{2n-2}$ as the following numbers, in order: $1$, $p+1$, $2p+1$, \dots, $n-p+1$ $2$, $p+2$, $2p+2$, \dots, $n-p+2$ \dots $p$, $2p$, $3p$, \dots, $n$. Then, every $\frac np$'th vertex will have safe move ``whistle'', and the rest will have safe move ``clap''. This completes the solution.
30.03.2021 06:46
$\textbf{Claim: }$ Ana wins for even $n.$ $\emph{Proof: }$ Just note that two turkeys separated by an odd number of positions will always have this property. $\blacksquare$ $\textbf{Claim: }$ Ana wins for odd composite $n.$ $\emph{Proof: }$ Let $d$ be a proper divisor of $n.$ Consider the sequence \begin{align*}S&=\{1,2,\dots,d-2,d,d-1\}\\&+\{d+1,d+2,\dots,2d-2,2d,2d-1\}\\&\vdots\\&+\{n-d+1,n-d+2,\dots,n-2,n,n-1\}\end{align*}Suppose Ana numbers $\textbf{every other}$ vertex of the polygon with the numbers of $S$ in order (where vertices are considered modulo $n$). Then it is easy to see that the polygon can be divided into pieces of $d$ consecutive vertices which are symmetric with respect to the conditions of the game. This implies that Beto will never be able to move turkeys from different pieces onto the same vertex, so Ana will win. $\blacksquare$ \ $\textbf{Claim: }$ Beto wins for prime $n.$ $\emph{Proof: }$ It suffices to show that given any two turkeys $A$ and $B$, Beto can reduce the even distance between them in finitely many moves. Label each vertex with a $1$ if its right neighbor is larger than its left neighbor and $0$ otherwise. Consider the following algorithm. If $A=1$ and $B=0$ or $A=0$ and $B=1,$ then either a clap or a whistle will reduce the even distance and we are done. If $A=1$ and $B=1$ or $A=0$ and $B=0,$ then either a clap or a whistle will shift segment $\overline{AB}$ clockwise (i.e. increase both $A$ and $B$ by $1$). Repeat with the new values of $A$ and $B.$ If this process never terminates, then all vertices that are a certain distance apart have the same label, which (since $n$ is prime) implies that all vertices have the same label. This is clearly a contradiction as Ana's tags must be a permutation of $1,2,\dots,n$. $\blacksquare$
28.09.2023 07:56
Rename Ana to Raiden from Metal Gear and Beto to Lisa from Blackpink. FTSOC suppose not. Label the numbers $a_1, a_2, \dots, a_n$. Claim: Lisa from Blackpink wins for prime $n \ge 3$. Proof. We show that given two turkeys with distance $k$, its possible to create distance $n + 2$ or $n - 2$ as desired for Lisa from Blackpink, taken $\pmod{p}$, which finishes by repeating. This is possible if the whistle ever causes the turkeys move in opposite directions. If the whistle causes the turkeys to move in the same direction, we can shift the two turkeys over one cyclically until this occurs, in which case we are done. FTSOC this never occurs, then this implies that $a_{i-1} > a_{i+1} \iff a_{i+k-1} > a_{i+k+1}$. However, since $n$ is prime this implies that $a_{i-1} > a_{i+1} \iff a_{i+1} > a_{i+3}$, creating a monotonic chain $a_0, a_2, \dots$, contradiction. $\blacksquare$ Claim: Raiden from Metal Gear wins if $n = ab$ is composite. Proof. Raiden from Metal Gear can simply make the relations between $a_0, a_2, \dots, a_{2n}$ cyclic with period $a$. This can be done by having it first increase $a-1$ times, then decrease once. Then the two turkeys with distance $a$ between them never meet. $\blacksquare$
09.10.2023 22:20
Beto wins if $n$ is prime, and otherwise Ana can win. Suppose that we have $n=ab$ with $a,b>1$ positive integers. Tag the vertices in the order $1,a+1,2a+1,\ldots,a(b-1)+1,2,a+2,\ldots,a(b-1)+2,\ldots,a,2a,\ldots,ab$. It is easy to see (by induction) that the turkeys that start at vertices $1$ and $2$ always move in the same direction, hence they never end up on the same vertex. Now suppose $n$ is a prime (hence odd). Let $v_1,\ldots,v_n$ be the vertices of the $n$-gon in order and let the numbers on them be $a_1,\ldots,a_n$. It suffices to show that we can move any two turkeys to the same vertex, whence we may merge them into a single turkey and repeat. Suppose each side of the $n$-gon has side length $1$. Take two arbitrarily placed turkeys (on different vertices) and consider the unique non-self-intersecting path $v_i,\ldots,v_j$ with even length between the two turkeys. Then Beto makes an action that moves the turkey from $v_i$ to $v_{i+1}$ and repeats this indefinitely, so the turkey originally at $v_i$ moves in the same direction around the polygon always. This will never decrease the length of this path (note that the turkeys can't move "over" each other), so if the turkeys never end up on the same vertex then the length of this arc must be eventually constant, say of length $l>0$. Since the turkey originally at $v_i$ visits every vertex of the polygon after the length of this arc becomes eventually constant, at which point the other turkey makes identical moves, it follows that for all $k$ we have $\mathrm{sgn}(a_{k-1}-a_{k+1})=\mathrm{sgn}(a_{k+l-1}-a_{k+l+1})$. Since $n$ is an odd prime, repeatedly applying this means that $\mathrm{sgn}(a_{k-1}-a_{k+1})$ is constant for all $k$. Thus if WLOG $a_1>a_3$, we find $a_1>a_3>a_5>\cdots>a_{2n-1}>a_{2n+1}=a_1$ (where indices are taken modulo $n$): absurd. Therefore Beto will eventually be able to merge the two turkeys, as desired. $\blacksquare$
12.04.2024 05:51
similar to above i think Beto wins iff $n$ is prime. $n$ is not a prime. Here, I claim that Ana wins. What she does is if $n=a\cdot b$ placing a $1$ in some spot, then place a $2$ $a$ steps counterclockwise. Repeat until a $b$, then then place $b+1$ to the left of the $1$, and repeat. This results in $1, 1+b, 1+2b, \dots, 1+(a-1)b, 2, 2+b, \dots$. Now, if we place a greater than or less than sign between each two numbers, rotating the grid $a$ cells gives a copy of the grid. Thus two turkeys starting $a$ away from each other can never merge together. $n$ is a prime. Here, I claim Beto can win. In fact, i claim the following. Claim: Beto can merge any two turkeys. Proof. Consider any two turkeys $A,B$ on a prime sized circle. Either their counterclockwise distance from $A$ to $B$ is even or their clockwise distance is even, so WLOG the counterclockwise distance from $A$ to $B$ is even. Then, the strategy for Beto is to always do the motion that moves $A$ counterclockwise. Indeed, the counterclockwise distance from $A$ to $B$ is always even after each step -- it decreases by $0$ or $2$. However, it can't always decrease by $0$ during a full circle by $A$, as that would imply that greater than/less than sign assignment from above is periodic. This contradicts $n$ being a prime. Thus as $A$ makes a full circle the counterclockwise distance from $A$ to $B$ is even and decreases, so it will eventually become $0$ and the two turkeys are merged. $\blacksquare$ Remark: This process in the claim is similar to a duck-duck-goose game: $A$ chases $B$ around the circle and eventually will catch up!
27.08.2024 19:04
Beto only wins if and only if $n$ is an odd prime. Note that the problme equates to being able to merge any two turkeys. For $2$ and any composite number, this is obviously impossible because we can force two opposite turkeys to go the same direction by repeating a pattern. Now we show that for all odd prime $n$ that Beto wins. Suppose there is some even distance $k$ that for any two turkeys $k$ apart, they can't get closer. Without loss of generality, let a clap at a starting position with two turkeys $k$ apart send them counter clockwise. Therefore, if we shift the turkeys $k$ clockwise, clapping will still send them counterclockwise. As $\gcd(k,n)=1$ we have that clapping at all points sends them counterclockwise, which obviuosly is impossible$.\blacksquare$
03.12.2024 00:57
Somehow my fastest solve in DCY-process was a 9-clubber
Attachments:

03.12.2024 01:05
Mathandski wrote: Somehow my fastest solve in DCY-process was a 9-clubber
Nice sol. Could you maybe add me I wanted to propose some other problems