Elmo and Elmo's clone are playing a game. Initially, $n\geq 3$ points are given on a circle. On a player's turn, that player must draw a triangle using three unused points as vertices, without creating any crossing edges. The first player who cannot move loses. If Elmo's clone goes first and players alternate turns, who wins? (Your answer may be in terms of $n$.) Proposed by Milan Haiman
Problem
Source: 2019 ELMO Shortlist C1
Tags: combinatorics, Game Theory, Elmo, combinatorics solved
28.06.2019 01:18
This one look very similar with Centro 2019/2!
05.07.2019 12:51
Really nice! pieater314159 wrote: Elmo and Elmo's clone are playing a game. Initially, $n\geq 3$ points are given on a circle. On a player's turn, that player must draw a triangle using three unused points as vertices, without creating any crossing edges. The first player who cannot move loses. If Elmo's clone goes first and players alternate turns, who wins? (Your answer may be in terms of $n$.) Proposed by Milan Haiman We claim that Elmo's clone, i.e. the first player always wins. We now prove this by giving a strategy for the clone. Let $n-3=2k+\varepsilon,$ where $\varepsilon \in \{0,1\}.$ Then the clone makes the triangle $(k,k,\varepsilon),$ i.e. the triangle which divides the circle into three arcs, two of which are left with $k$ points and the last with $\varepsilon$ points. Clearly, the arc with $\varepsilon$ points will never be touched. So now the clone, acting as a clone, copies each move that Elmo performs by choosing the same points for a triangle as Elmo but in the opposite arc. We claim that this works. Firstly, note that since the clone copies Elmo's moves, each of his moves is defined and possible. Now assume that Elmo exhausts one arc, i.e. not more triangles can be formed in it. Then in the next move, his clone will exhaust the other arc and so would win. Also, the clone cannot be the first one to exhaust an arc. Hence this strategy works and the clone wins. $\blacksquare$ Clarification: For instance for $n=10,$ we have $k=3, \varepsilon=1$ and the triangle $(3,3,1)$ looks like: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -15.130319137744937, xmax = 10.196487272490442, ymin = -11.516802752350074, ymax = 4.990202377061246; /* image dimensions */ pen ccqqqq = rgb(0.8,0,0); draw((-7.057619125469231,4.14975378783924)--(-11.679332177825689,-6.131145940071269)--(-2.0680624110280243,-6.03654357000303)--cycle, linewidth(0.4) + ccqqqq); /* draw figures */ draw(circle((-6.91296329960006,-2.0945560288466774), 6.245985142050692), linewidth(0.4)); draw((-7.057619125469231,4.14975378783924)--(-11.679332177825689,-6.131145940071269), linewidth(0.4) + ccqqqq); draw((-11.679332177825689,-6.131145940071269)--(-2.0680624110280243,-6.03654357000303), linewidth(0.4) + ccqqqq); draw((-2.0680624110280243,-6.03654357000303)--(-7.057619125469231,4.14975378783924), linewidth(0.4) + ccqqqq); /* dots and labels */ dot((-7.057619125469231,4.14975378783924),dotstyle); dot((-9.753897545259518,3.467945477360519),dotstyle); dot((-12.117407980094821,1.3588605348461216),dotstyle); dot((-3.6959005756989582,3.2592125340633804),dotstyle); dot((-1.6163784923000994,1.215809475715809),dotstyle); dot((-6.840340474825683,-8.34011895944307),dotstyle); dot((-11.679332177825689,-6.131145940071269),dotstyle); dot((-2.0680624110280243,-6.03654357000303),dotstyle); dot((-13.158901525038415,-2.1187650917359737),dotstyle); dot((-0.6677115449139137,-1.9988433582767742),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy]
18.01.2020 00:45
First see that if a player has a winning strategy then the other player has a losing strategy. We use induction on $n$ to show that first player wins. For $n\leq 9$ the first move will finish the game. Assume that the first player wins for all $n<k$ For $n=k$ , Chose two consecutive points $A,B$ and a third point $C$ such that there are three points between $A$ and $C$ . Call the three points good island and the remaining points bad island. Note that only one move is permitted on good island and that there are $k-3> 3$ points on the bad island Now it is the move of the second player and he will play something, player one will only proceed on bad island . Case I - Player 2 plays a move on good island . This will leave the board in a condition where it is first player to play on bad island instead of second player who actually had winning strategy by induction. And hence first player will win. Case II - Player 2 never plays a move on good island . Then player 1 would lose on bad island and then play a move on good island winning the game.
09.05.2020 01:30
The hardest part of this problem is remembering that Elmo's clone goes first. Elmo's clone always wins. If $n$ is odd: For his first move, he must pick two adjacent vertices and pick the third vertex such that it partitions the circle into two arcs with $\frac{n-3}{2}$ unused points each. Then he wins by mirroring Elmo's moves - if Elmo can move his clone can move, and if Elmo can't move the clone wins. If $n$ is even: For his first move, he must pick three vertices such that the remaining vertices are partitioned into groups of $\frac{n-4}{2},\frac{n-4}{2},1.$ Then he wins by mirroring Elmo's moves - if Elmo can move his clone can move, and if Elmo can't move the clone wins.
19.08.2020 21:43
pieater314159 wrote: Elmo and Elmo's clone are playing a game. Initially, $n\geq 3$ points are given on a circle. On a player's turn, that player must draw a triangle using three unused points as vertices, without creating any crossing edges. The first player who cannot move loses. If Elmo's clone goes first and players alternate turns, who wins? (Your answer may be in terms of $n$.) Proposed by Milan Haiman Let $n = 2z + t$, where $t \in \mathbb{Z} _2$. We number the points as $a_1, a_2, a_3 \dots a_n$ and ELMO's clone draws the triangle $a_i, a_j, a_k$ such that the number of points in the arc $a_i a_j$ not containing $a_k$ has $t$ points, exclusive kf $a_i, a_j$ and the arcs $a_ia_k$ and $a_ja_k$ not containing $a_j$ and $a_i$ respectively contains equal number of points. In this way, ELMO can never draw a triangle contained by $a_ia_j$ arc as $t \in \mathbb{Z} _2$ and whatever ELMO does on arc $a_ia_k$ or arc $a_ja_k$, ELMO's clone copies it onto the other arc $a_ja_k$ or $a_ia_k$ respectively implying that ELMO's clone always wins. ELMO's clone : Vrag szadi po levomo fangul!
31.08.2021 08:55
dchenmathcounts wrote: The hardest part of this problem is remembering that Elmo's clone goes first. I can personally attest to this; the last sentence on my scrap paper is, "Shoot Elmo doesn't go first!" Elmo's Clone always wins. Label the vertices as $1, 2, \ldots, n$. If $n = 2k$, then let the clone pick vertices $\{2, k+1, 2k\}$. Clearly, the vertice labeled $1$ cannot be selected, and the rest of the vertices have been split into $2$ sub-groups consisting of $k-2$ consecutive vertices each. Now, a simple mirroring technique wins for Elmo's Clone. If $n = 2k-1$, then let the clone pick vertices $\{1, k, 2k-1\}$. At this point, the rest of the vertices have been split into $2$ sub-groups consisting of $k-2$ vertices each. Now, a simple mirroring technique wins for Elmo's Clone. $\blacksquare$
31.08.2021 15:22
beautiful problem I finally solved a combo game problem First, start by renaming Elmo with Santa and his clone with Banta. We claim that Banta has a winning strategy. Let the number of vertices be $2n+k, k \in \{0.1\}$. Banta starts by making a triangle, which divides the arcs such that two of them contain $n$ points and the other contains $k$ points. This renders the arc with $k$ points unusable. Now, Banta just mirrors Santa’s moves in the other arc. FTSOC assume Banta was not able to make a valid triangle at some point. This would mean that Santa made the same kind of triangle in both the arcs, impossible $\blacksquare$
24.11.2022 21:14
We claim Elmo's clone always wins. Number the point $1,2,\dots,n$ and if $n$ is even, Elmo's clone can choose $1,3,$ and $\frac{n-4}{2}+4$ leaving the points from $4$ to $\frac{n-4}{2}+3$ inclusive and $\frac{n-4}{2}+5$ to $n$ inclusive. Notice both intervals have an equal number of points, so Elmo's clone can now mirror Elmo. If $n$ is even, Elmo's clone can choose $1,2,$ and $\frac{n-3}{2}+3$ to create the two intervals of points from $3$ to $\frac{n-3}{2}+2$ inclusive and $\frac{n-3}{2}+4$ to $n$ inclusive. Again, both intervals have the same number of points, so Elmo's clone can now mirror Elmo. $\square$
27.11.2022 19:44
This solution is motivated by the simple fact that every number is either odd or even. Let Elmo's clone be Player 1 and Elmo be Player 2 for simplicity. We claim that Player 1 always wins. On the first most, Player 1 should isolate one of the $3$ arcs created and create $2$ identical arcs. Thus, since $n-3=2k+c$ for some $k \in \mathbb{N}^+$ and $c \in {0,1}$ (using our "key motivation" above), Player $1$ can create $2$ symmetrical arcs and close off $1$ arc. Each of Player 1's moves will clearly be "legal", since Player 2 made the same move on the other (identical) arc. Thus, both arcs in play will be symmetrical after every move by Player 1, which means that when the first person gets stuck, it will be Player 2. $\blacksquare$
19.12.2022 04:46
Elmo's clone always wins. Obviously for $n \leq 8$ Elmo's clone can just pick three points on the circle such that there are less than three points in each of the three sectors his triangle cuts the circle into, so Elmo is unable to pick another triangle. For $n \geq 9$, let Elmo's clone pick a vertex and the two vertices nearest to diametrically opposite it if $n$ is odd, and the two vertices that are adjacent to the vertex diametrically opposite it if $n$ is even. Now Elmo's clone can just copy Elmo's moves on the other sector of the circle, like he is supposed to do anyways, right?
13.04.2023 01:19
02.06.2023 20:43
The answer is that Elmo’s clone always wins. We define a “valid” position as a position which still allows a player to move. We then have 2 cases. Case 1: can divide n into valid positions after move 1. This means n ≥ 9 (8 and 7 does work but these positions are losing). The strategy here is to abuse symmetry. If n is odd, We position the triangle such that the points on the arcs cut off by the triangle are of the form 0, (n-3)/2, and (n-3)/2. For even we leave it as 1, (n-4)/2, (n-4)/2. Then Elmo’s clone just need to mirror Elmo on the parts which are equal. Case 2, n ≤8 Manually all of these can be shown to be true.
05.08.2023 20:47
Split according to the parity of $n$. The main idea is that we want to introduce symmetry so that Elmo's clone can copy Elmo whenever Elmo makes a move. If $n$ were even, then have Elmo's clone pick a triangle which are two vertices that two apart and is isosceles (example shown in diagram). If $n$ were odd, then have Elmo's clone pick a triangle which are one vertex above from each other and is isosceles (again, in figure). (sorry for drawing potatoes instead of actual circles :cri: ) Now, Elmo can't pick from the "shortest side's arc", so Elmo must pick from one of the longer equal arcs. If Elmo picks something, then Elmo's clone can also pick something, therefore Elmo's clone will always win.
30.12.2023 12:04
The clone always wins. If $n$ is odd, then the clone draws the triangle as in the diagram below. Then after Elmo makes a move, the clone just copies the move in the other half of the circle. If $n$ is even, then the clone draws the triangle as in the diagram below. Then the clone similarly copies Elmo's moves on the other side of the two halves that are created. So the clone always wins.
03.08.2024 00:40
Elmo's clone always wins for all $n.$ If $n$ is odd, then take the two ends of one side of the $n$-gon and look at the point opposite it, and make Elmo's clone construct the triangle formed by these three points. This splits the circle into two regions, each with $\frac{n-3}{2}$ points. If Elmo moves in one half, then his clone performs the exact same move in the other half, giving a winning strategy for the clone. Similarly, if $n$ is even, then take on point of the $n$-gon, look at the two points adjacent to its antipode, and make Elmo's clone construct the triangle with those three points. This splits the circle into two regions, two with $\frac{n-4}{2}$ points and one with $1$ point. No player can operate in the region with $1$ point, and Elmo's clone repeats the same strategy as above; if Elmo moves in one half, then his clone moves in the other half. Therefore, Elmo's clone has a winning strategy for all $n,$ and thus the clone always wins.
24.11.2024 06:47
Cool problem! Sorry Elmo . Elmo's clone will choose an isosceles triangle so that its base cuts off either $0$ or $1$ points, where $n$ is odd or even. Now, whenever Elmo makes a move, Elmo's clone will copy that move on the other side of the triangle.
27.11.2024 19:46
Nice problem! I think the point is that Elmo lost the game. We claim that Elmo's clone wins for all positive integers $n$. Starting from an arbitrary vertex on the circle, we label the points $1,2,\dots ,n$ going clockwise. If $n$ is odd, Elmo's clone draws the triangle connecting the points $1$ , $\frac{n+1}{2}$ and $\frac{n+3}{2}$. If $n$ is even, Elmo's clone draws the triangle connecting the points $1$ , $\frac{n}{2}$ and $\frac{n+2}{2}$. Now, note that the set of points is divided into two regions. Due to the conditions of the problem, any new triangle drawn must have three points from the same region. Whenever Elmo does a move in one of these regions, Elmo's clone replies by mirroring his move on the other region. Since the configuration is symmetric, this guarantees Elmo's clone a move as long as Elmo has a valid move. Thus, Elmo runs out of valid moves first, and Elmo's clone always wins.
28.11.2024 19:42
A symmetry argument may be used to show that Elmo's clone always wins.