For an integer $n \geq 5,$ two players play the following game on a regular $n$-gon. Initially, three consecutive vertices are chosen, and one counter is placed on each. A move consists of one player sliding one counter along any number of edges to another vertex of the $n$-gon without jumping over another counter. A move is legal if the area of the triangle formed by the counters is strictly greater after the move than before. The players take turns to make legal moves, and if a player cannot make a legal move, that player loses. For which values of $n$ does the player making the first move have a winning strategy?
Problem
Source: 7th RMM 2015, Problem 2
Tags: combinatorics, RMM, combinatorial geometry, RMM 2015
28.02.2015 20:36
for $n=3k+2$ I think a strategy that forces the player making the second move to increase the smallest distance between the 3 counters at every step works.
01.03.2015 07:04
Recast the game as one about triples of numbers by taking the angles of the triangles in radians and multiplying them by $n/\pi$. This gives us three positive integers summing to $n$. We start with $1, 1, n-2$, and the game ends when we get $[n/3], [(n+1)/3]$, $[(n+2)/3]$ where $[n]$ denotes the floor of $n$. A move is choosing two numbers and moving them closer together while keeping them integers with the same sum.
(EDIT: now that I've taken the time to iron out the details, I think OHO's post is correct)
01.03.2015 12:34
I have a different answer. Write $n=3+2^k m$ where $m$ is odd. Then the first person wins if and only if $k$ is odd. Simplify the game the same way as MellowMelon, and prove that $x\geq y\geq z$ is a losing position if and only if $\{x-y,y-z\}=\{0,2^k m\}$ for some $m$ odd and $k$ even. The proof is by induction on $x-z$. 1. If $\{x-y,y-z\}=\{0,2^k m\}$ for some $m$ odd and $k$ even then any move will bring it to $x'\geq y'\geq z'$ with $\{x'-y',y'-z'\}\not=\{0,2^{k'} m'\}$ for all $m'$ odd and $k'$ even. Done by induction since $x'-z'<x-z$. 2. If $\{x-y,y-z\}=\{0,2^k m\}$ for some $m$ odd and $k$ odd then (by replacing $x,z$ with $\frac{x+z}{2},\frac{x+z}{2}$) it can be moved to $x'\geq y'\geq z'$ with $\{x'-y',y'-z'\}=\{0,2^{k-1} m\}$. 3. If $0\not\in\{x-y,y-z\}$ then we move it to either $(y,y,x+z-y)$ or $(y,\frac{x+z}{2},\frac{x+z}{2})$. One of these has the form $x'\geq y'\geq z'$ with $\{x'-y',y'-z'\}=\{0,2^{k'} m'\}$ for some $m'$ odd and $k'$ even because their $\max-\min$ are $|x+z-2y|$ and $\frac{|x+z-2y|}{2}$.
01.03.2015 15:25
@ above : What if $x+z$ is odd for your 3rd case?
01.03.2015 17:02
If $x+z$ is odd then $(y,y,x+z-y)$ works because $\max-\min=|x+z-2y|$ is odd.
31.03.2015 16:59
Is there a more constructive way to show the answer (i.e. one where the answer doesn't appear to fall from the sky)?
31.03.2015 17:29
http://rmms.lbi.ro/rmm2015/index.php?id=solutions_math One may notice the answer by checking the small value of n(n<25 ),but that would take a lot of time
08.02.2016 16:03
The answer is that the first player wins iff $v_2(n-3)$ is odd. The motivation for this will be made clear in the following solution: First we rephrase the question as follows: Given a triple of positive integers $(a,b,c)$ with $a+b+c=n$, a legal move consists of replacing two of $a$, $b$, and $c$ with two other numbers that add to the same value but have a smaller difference. Initially the triple $(n-2,1,1)$ is given, both players alternate making a legal move, and whoever cannot make a legal move loses. This is equivalent to the problem because $(a,b,c)$ corresponds to the triangle that, when traversing counterclockwise along the circumcircle of the $n$-gon, has $\frac{2a\pi}{n}$, $\frac{2b\pi}{n}$, and $\frac{2c\pi}{n}$ as arcs between consecutive vertices. Now, say that two triples of integers $(a,b,c)$ and $(x,y,z)$ are equivalent if every legal move on $(a,b,c)$ corresponds to a legal move on $(x,y,z)$ and vice versa. Denote by $(a,b,c)\sim(x,y,z)$ the equivalence of $(a,b,c)$ and $(x,y,z)$. Clearly, $(a,b,c)\sim(a_0,b_0,c_0)$, where $a_0,b_0,c_0$ is any permutation of $a,b,c$. Lemma: If $k$ is any integer, then $(a,b,c)\sim(a+k,b+k,c+k)$ and $(a,b,c)\sim(-a,-b,-c)$. Proof: The legal move $(a,b,c)\rightarrow(a+i,b-i,c)$ corresponds to $(a+k,b+k,c+k)\rightarrow(a+k+i,b+k-i,c+k)$ and $(-a,-b,-c)\rightarrow(-a-i,-b+i,c)$ respectively. As a corollary, $(a,a,0)\sim(-a,-a,0)\sim(0,0,a)\sim(a,0,0)$. Now, note that $(n-2,1,1)\sim(n-3,0,0)$ by the lemma. Let $m=n-3$. By examining small cases, we notice that the first player wins the game of $(m,0,0)$ iff $v_2(m)$ is odd, and we will prove this by strong induction. Throughout the induction, we say that a player wins if they make a legal move that results in a triple that is equivalent to $(0,0,0)$ or $(1,0,0)$. This is clearly equivalent to the winning condition of the problem. For the base cases, note that for $(2,0,0)$, the first player makes the move $(2,0,0)\rightarrow(1,1,0)\sim(1,0,0)$ and wins. For $(3,0,0)$, the first player is forced to make the move $(3,0,0)\rightarrow(2,1,0)$, and the second player wins by making the move $(2,1,0)\rightarrow(1,1,1)\sim(0,0,0)$. For the inductive step, we will show that if $v_2(m)$ is odd, then the first player can give the second player the triple $(m',0,0)$ where $v_2(m')$ is even and $m'<m$. This is now equivalent to the second player going first with a triple that results in a loss for the first player by the inductive hypothesis. We will show that the opposite is true if $v_2(m)$ is even. Suppose that $v_2(m)$ is odd. Then, $2\mid m$, so the first player can make the move $(m,0,0)\rightarrow\left(\frac{m}{2},\frac{m}{2},0\right)\sim\left(\frac{m}{2},0,0\right)$. Because $v_2\left(\frac{m}{2}\right)$ is even, we are done. Suppose that $v_2(m)$ is even. Then, the first player must make the move $(m,0,0)\rightarrow(m-k,k,0)$ for some positive integer $k<m$. Without loss of generality, suppose that $m-k\geq k$. If $m-k$ is odd, then the second player makes the move $(m-k,k,0)\rightarrow(m-2k,k,k)\sim(m-3k,0,0)\sim(|m-3k|,0,0)$. Since $|m-3k|$ is also odd, we are done. If $m-k$ is even, then the second player can either make the move $(m-k,k,0)\rightarrow(m-2k,k,k)\sim(m-3k,0,0)\sim(|m-3k|,0,0)$ or the move $(m-k,k,0)\rightarrow\left(\frac{m-k}{2},k,\frac{m-k}{2}\right)\sim\left(k,\frac{m-k}{2},\frac{m-k}{2}\right)\sim\left(\frac{3k-m}{2},0,0\right)\sim\left(\frac{|m-3k|}{2},0,0\right)$. Because one of $v_2(|m-3k|)$ and $v_2\left(\frac{|m-3k|}{2}\right)$ is even, the second player can always force the first player into a losing position by the inductive hypothesis, so we are done.
12.04.2017 18:54
04.05.2020 05:19
Let $a,b,c$ be the arc lengths between the three counters, so in particular, $a,b,c$ are all positive integers that sum to $n$. The information of the state of the counters is fully captured by the multiset $\{a,b,c\}$. A move consists of replacing two of the elements $x$ and $y$ with $x'$ and $y'$ such that $(x')^2+(y')^2<x^2+y^2$ (or whatever). Due to the monovariant $a^2+b^2+c^2$, we see that the game must eventually stop. We have the following claim that classifies all winning positions. Claim: The losing positions are exactly \[\{k,k,n-2k\}\]where $1\le k<n/2$ and $v_2(n-3k)$ is even or infinite. Proof: Call a position losing if it satisfies the above criteria, and winning otherwise. Since the game terminates after a finite amount of moves, it suffices to verify three things. Any position that has no further moves available is losing. Any move from a losing position leads to a winning position. For any winning position, there is some move that leads to a losing position. We begin by proving the first item. Indeed, a position which has no further moves available is one of \[\{\ell,\ell,\ell\},\{\ell,\ell,\ell+1\},\{\ell,\ell+1,\ell+1\},\]all of which can be checked to be losing. We now verify the second item. Suppose we are in the losing position $\{k,k,n-2k\}$ where $v_2(n-3k)$ is even. Indeed, only states which have two equal numbers have the potential to be losing, so the only possible states that are one move from $\{k,k,n-2k\}$ and are not winning are \[\left\{k,\frac{n-k}{2},\frac{n-k}{2}\right\},\{4k-n,n-2k,n-2k\}.\]However note that \[v_2\left(n-3\frac{n-k}{2}\right)=v_2\left(\frac{3k-n}{2}\right)=v_2(n-3k)-1\]and \[v_2\left(n-3(n-2k)\right)=v_2\left(6k-2n\right)=v_2(n-3k)+1,\]both of which are odd. Thus, all positions one move away from $\{k,k,n-2k\}$ are winning, as desired. We now verify the third item. There are two (similar) cases. Case 1: Suppose we are in the winning position $\{a<b<c\}$. Replace $\{a,c\}$ with $\{b,n-2b\}$, which is a valid move since $a<b<c$. If $\{b,b,2n-b\}$ is losing, then we are done. Thus, we may suppose WLOG that it is winning, so \[v_2(n-3b)=v_2(a+c-2b)\]is odd. In particular, $a+c\equiv 2b\pmod{2}$, so $a+c\equiv 0\pmod{2}$. We now claim that the position \[\left\{b,\frac{a+c}{2},\frac{a+c}{2}\right\}\]is losing, which finishes. Indeed, \[v_2\left(n-3\frac{a+c}{2}\right)=v_2\left(\frac{2b-a-c}{2}\right)=v_2(a+c-2b)-1,\]which is even, as desired. Case 2: Suppose we are in the winning position $\{k,k,n-2k\}$ (so $k\ne n-2k$). Thus, we have $v_2(n-3k)$ odd, so in particular, $n\equiv k\pmod{2}$. So we may apply a move to go the position \[\left\{k,\frac{n-k}{2},\frac{n-k}{2}\right\}.\]This is losing as \[v_2\left(n-3\frac{n-k}{2}\right)=v_2\left(\frac{3k-n}{2}\right)=v_2(n-3k)-1,\]which is even, as desired. This proves the third item, which completes the proof of the claim. $\blacksquare$ To finish, we see that the first player wins if and only if $\{1,1,n-2\}$ is winning, or that $v_2(n-3)$ is odd. Remark: The hardest part of the problem is to find the claim. I could only do this by bashing out all the positions and finding which ones are winning and losing for $5\le n\le 16$. Once I found the claim though, proving it was straightforward.
23.12.2020 05:11
Remark: Totally worth doing. Note that each position can be uniquely defined by an ordered triple $(i, j, k)$, where $i, j, k$ are the number of arcs between counters, pairwise, where the numbers always satisfy $i + j + k = n$. The initial position is described by $(n-2, 1, 1)$. Furthermore, valid move consists of choosing two of $i, j, k$ from $(i, j, k)$, WLOG $i < j$, keeping their sum constant, but making their difference $j - i$ smaller. Furthermore, note that the state of the position $(a, b, c)$ (winning or losing) is the same as any position of the form $(a + \ell, b + \ell, c + \ell)$ where $\ell$ can be any integer, or of the form $(-a, -b, -c)$, since only differences between the numbers matter. Thus, we want to find when $(n-2, 1, 1) = (n-3, 0, 0)$ is a winning position. I claim that in general, the position $(x, 0, 0)$ is winning if and only if $v_2(x)$ is odd. We will do this with induction. The base case clearly holds. Now, suppose this claim holds true for all $x < m$ for some $m$. If $v_2(m)$ is odd, we will show player $1$ can force player $2$ into to a losing position. Player $1$ can move to\[(\tfrac{m}{2}, \tfrac{m}{2}, 0) = (0, 0, -\tfrac{m}{2}) = (\tfrac{m}{2}, 0, 0)\]and since $v_2(\tfrac{m}{2}) = v_2(m) - 1$ is clearly even, this next positition for player $2$ is losing, so indeed $(m, 0, 0)$ is winning. If $v_2(m)$ is even, we will show player $2$ can force player $1$ into a losing position. Player $1$'s must move to a position of the form $(m-i, i, 0)$ where $i < \tfrac{m}{2}$. If $m-i$ is odd, then player $2$ can move to $(m-2i, i, i) = (m-3i, 0, 0)$ and since $m-i$ is odd, so is $m-3i$, and thus $v_2(m-3i) = 0$ is even. Hence, player $1$ is forced into a losing position. If $m-i$ is even, then player $2$ either copy the previous case and move to $(m-2i, i, i) = (m-3i, 0, 0)$, or he can move to\[(\tfrac{m-i}{2}, i, \tfrac{m-i}{2}) = (0, \tfrac{3i-m}{2}, 0) = (\tfrac{m - 3i}{2}, 0, 0).\]Note that $v_2(m-3i)$ and $v_2(\tfrac{m-3i}{2})$ are consecutive so one of them is even and thus one of the moves leads to a losing position. So player $2$ chooses that move and force player $1$ into a losing position. We have exhausted all cases in the necessary inductive step, so we have proven our claim. So indeed, for the original problem, player $1$ wins when $v_2(n - 3)$ is odd. $\blacksquare$
23.12.2020 09:00
FWIW, I think it's worth mentioning that the "characterization of all winning / losing positions" may be much simplified by noting that we can take a geometrical approach, by expressing all the triples in terms of the corresponding coordinates in the triangle for Dumbass Notation (the one in inequalities). This gives us a way to induct up, as we can continue just adding "rings" (a.k.a. adding 3 to the overall side length of the triangle) to the triangle, and this triangle of the $n+3$ case will still have the same "states of the game" as the triangle of the $n$ case inscribed within it. This does need some casework though, as the $3$ cases (separated $\bmod 3$) should (?) be done independently.
26.05.2021 07:51
07.07.2021 22:44
Let A be the player that moves first and B be the player that moves second. We will prove that A wins if and only if $v_2(n-3)$ is odd. As in previous solutions, rephrase the problem in terms of integer triples; but for convenience, we further reduce all three entries by 1 (so any legal position $(a,b,c)$ has sum $a+b+c=n-3$). We first prove the following magical claim: Claim. Suppose that some player (say A) is faced with a position $(a,b,c)$ at some point, where $a\le b\le c$. If $a<b<c$ (call such situations bad), then A wins. Proof: Because $a<b<c$, the move $(a,b,c) \to (b,b,c+a-b)$ is legal. Now, suppose that A performs this move. If A wins from here on, then we are done. If A loses and B can win by responding $(b,b,c+a-b) \to (b,d,c+a-d)$, then A instead moves $(a,b,c) \to (b,d,c+a-d)$. This is clearly a legal move since it is the composition of two legal moves, and A wins in this case as well. $\square$ Now, we return to the problem. As an example, consider the case where $n$ is even. Then A's first move must result in a bad position, so B wins. For the general situation $n = 3 + 2^k p$ where $p$ is odd, based on our previous analysis, the optimal moves for both players are \[(0,0,2^kp) \to (0, 2^{k-1}p, 2^{k-1}p) \to (2^{k-2}p, 2^{k-2}p, 2^{k-1}p)\to (2^{k-2}p, 3\cdot 2^{k-3}p, 3\cdot 2^{k-3}p) \to \dots\]It is easy to see by induction that at each step, the three entries will include one odd multiple of $2^i$ and two equal odd multiples of $2^{i-1}$ for some $i$. Eventually one of the players would not be able to continue this, and the first player who depletes the powers of 2 wins. In other words, A wins if and only if $k$ is odd.
25.12.2023 22:35
Despite this problem being somewhat easy, it is easily a masterpiece. The answer is all $n \ge 5$ such that $\nu_2(n-3)$ is odd. Part 1: Encoding the problem Understand each configuration as a game ``starting" with a triple $(a, b, c)$, where $a$, $b$, and $c$ are integers that denote the ratio of arc angles between the token positions such that $a+b+c=n$. We say that $(a, b, c)=(d, e, f)$ if and only if both configurations lead to Ash having a winning strategy or both lead to Ash not having a winning strategy. The area condition encodes as follows: a move is legal if and only if two of $a$, $b$, $c$ can be modified to have a smaller positive difference while keeping the same sum. Part 2: Triple equivalence properties What we can do is take an extension of the set of triples $(a, b, c)$ where we permit negatives; this way, we can prove equivalences more easily while keeping all calculations valid. We have the following properties: 1. $(a, b, c)=(b, c, a)=(c, a, b)$; 2. $(a, b, c)=(a+\delta, b+\delta, c+\delta)$ for any integer $\delta$; 3. $(a, b, c)=(-a, -b, -c)$. These are enough for us to prove that the set of desirable $n$ is the claimed one. Part 3: Triple chasing For each $n \ge 5$, write $m=(n-3)/2^{\nu_2(n-3)}$. Then triple chase as follows: \begin{align*} (n-2, 1, 1) = (n-3, 0, 0) = (2^{\nu_2(n-3)} \cdot m, 0, 0) = (2^{\nu_2(n-3)-1} \cdot m, 2^{\nu_2(n-3)-1} \cdot m, 0) \\ = (2^{\nu_2(n-3)-1} \cdot m, 2^{\nu_2(n-3)-2} \cdot m, 2^{\nu_2(n-3)-2} \cdot m) = (2^{\nu_2(n-3)-1} \cdot m, 2^{\nu_2(n-3)-2} \cdot m, 2^{\nu_2(n-3)-2} \cdot m) \\ = (2^{\nu_2(n-3)-2} \cdot m, 0, 0). \end{align*}Repeating the above iteratively, we find that \[ (n-2, 1, 1) = (2^{\nu_2(n-3) \bmod{2}}, 0, 0) = (2^{\nu_2(n-3) \bmod{2}}+1, 1, 1), \]so working out the RHS by hand, we find that $(n-2, 1, 1)$ has a winning strategy if and only if $\nu_2(n-3)$ is odd, as desired.