There are $m \ge 2$ blue points and $n \ge 2$ red points in three-dimensional space, and no four points are coplanar. Geoff and Nazar take turns, picking one blue point and one red point and connecting the two with a straight-line segment. Assume that Geoff starts first and the one who first makes a cycle wins. Who has the winning strategy?
Problem
Source: 2017 Korean Winter Program Practice Test 1 Day 1 #2
Tags: combinatorics, Combinatorial games, graph theory
27.01.2017 08:00
Just making 4-cycles kills this problem The answer differs when $ m,n $ is odd/even.
03.10.2017 16:12
toto1234567890 wrote: Just making 4-cycles kills this problem The answer differs when $ m,n $ is odd/even. Can you elaborate more please? (Why nobody post problems of Test 2?)
03.10.2017 19:23
thre is not clarity in the question, do they connect a blue and a red or blue blue and red red ?
04.10.2017 15:42
First, translate this problem to its graph theoretic version because why do you need 3D space. Geoff wins if $m, n$ are both odd and Nazar wins otherwise. First, notice the following: if we have a path $R_1 B_1 R_2 B_2$, the next player to move immediately wins by connecting $R_1 B_2$, forming a 4-cycle. Moreover, if someone forms a cycle, right before that there must be a path of length 3. Thus whoever makes a path of length 3 loses, and as long as someone doesn't make a path of length 3, they don't lose on the next move. Armed with this, these are the strategies respectively. Call a vertex clean if it doesn't have any drawn edge incident to it yet, and dirty otherwise. For Geoff, when $m,n$ are both odd, first he draws any edge. Now Nazar has three kinds of possible moves: If Nazar draws an edge that makes a path of 3, Geoff immediately wins by completing the cycle. If Nazar draws an edge $(b,r)$ where $b$ is dirty (but $r$ is clean, since otherwise that would be a path of length 3), then Geoff draws an edge $(b,r')$ with the same $b$, and some other clean $r'$. Here $b$ can be blue or red (my naming suggests blue, but it can be reversed); $r$ and $r'$ have the same color, opposite of $b$. If Nazar draws an edge $(b,r)$ where both vertices are clean, then Geoff draws another edge $(b', r')$ where both vertices are also clean. The first option clearly gives Geoff the win. We claim Geoff can always make a reply in the latter two options, and moreover it will not make a path of length 3. This means Geoff will not be the first person making a path of length 3, and thus Nazar must be, giving Geoff the win. The trick is that $m,n$ are both odd. After the first edge, there are an even number of clean vertices of each color remaining. Whenever Nazar uses some (from the second or third options), that leaves an odd number of clean vertices of the respective color; in particular, this is at least one, so Geoff can use another clean vertex of the same color. Moreover, in the third option, clearly Geoff is in no risk of making a path of length 3 (both endpoints were clean), and in the second option, if Geoff makes a path of length 3, then Nazar must have also made a path of length 3 with his move, and thus Geoff would have stolen the win first. This gives a winning strategy for Geoff. If at least one of $m,n$ are even, then Nazar wins. WLOG assume $n$, the number of red points, is even. Nazar's strategy is simple. If Geoff makes a play $(b,r)$ where $b$ is blue and $r$ is red, then Nazar either grabs the win if that was a path of length 3, or otherwise Nazar plays $(b,r')$ where $r'$ is a fresh vertex. The trick is that after every of Nazar's moves, all dirty blue vertices have degree at least 2 among the drawn edges. Say $b$ is blue, then it will have edges connecting to at least two other red vertices, $r_1, r_2$. If Geoff uses one of these red vertices, that gives a path of length 3 and Nazar wins. Thus Geoff can't use any dirty red vertex, and so is forced to use clean red vertices. This also means all dirty red vertices have degree 1, and so Nazar's reply won't make a path of length 3. Since there are an even number of red vertices, and whenever Geoff uses one, Nazar also uses one, we deduce that Nazar will always have a clean red vertex available. This gives a winning strategy for Nazar.