A 2-player game is played on $n\geq 3$ points, where no 3 points are collinear. Each move consists of selecting 2 of the points and drawing a new line segment connecting them. The first player to draw a line segment that creates an odd cycle loses. (An odd cycle must have all its vertices among the $n$ points from the start, so the vertices of the cycle cannot be the intersections of the lines drawn.) Find all $n$ such that the player to move first wins.
Problem
Source: 2019 Canadian Mathematical Olympiad Problem 5
Tags: Game Theory, game strategy, Combinatorial games, graph theory, graph cycles, combinatorics
62861
31.03.2019 03:39
I think this works.
Let $A$ and $B$ denote the first and second player. We will prove that $A$ wins with best play if and only if $n \equiv 2 \pmod{4}$.
First of all, observe that the final state of the game is a complete bipartite graph $K_{a, b}$ with $a + b = n$. This means that $A$ wins if only if $a$ and $b$ are both odd.
Define a balanced connected bipartite graph (on more than 1 vertex) to be one where both color classes have equal cardinality. We also say a general bipartite graph is balanced if each nontrivial connected component (of more than 1 vertex) is balanced.
Claim. If $n$ is odd then $B$ wins.
Proof. If the final state is $K_{a, b}$, one of $a$ and $b$ must be even.
Lemma. If $n$ is even, then either player $S \in \{A, B\}$ can force the final state $K_{n/2, n/2}$.
Proof. Let $T$ be the other player.
The strategy for $S$ is to ensure that the graph is always balanced after their turn (in particular, there are an even number of isolated vertices); certainly this is true at the outset. To see this is always possible, we take two cases on $T$'s move.
If $T$ joins an isolated vertex to a nontrivial connected component $\gamma$, then $S$ can simply connect another isolated vertex to the opposite color class in $\gamma$.
Otherwise, $T$ leaves the graph balanced. In this case, $S$ may draw a new edge involving zero or two isolated vertices; this leaves the graph balanced.
Thus $S$ can always ensure the graph is balanced on their turn, forcing the final state $K_{n/2, n/2}$.
Corollary. If $n \equiv 2 \pmod{4}$ then $A$ wins. If $n \equiv 0 \pmod{4}$ then $B$ wins.
The desired conclusion follows.
r3mark
31.03.2019 03:51
Similar to above
When $n$ is odd, player 2 wins with the following strategy: each turn, if the graph is not yet fully connected, he connects two connected components. Once the graph is fully connected, it must be a bipartite graph so we can color the vertices black and white as usual. Since there are an odd number of vertices, either the number of black vertices is even, or the number of white vertices. An edge is valid only if it connects a black vertex and a white vertex, otherwise an odd cycle is formed. There are an even number of valid edges (number of black vertices times number of white vertices), so player two can keep drawing valid edges and player one will be the first to be unable to play.
When $n$ is even, let us first consider the case where $n \equiv 2 \pmod{4}$. Pair up the vertices and denote $A^\ast$ to be the vertex paired with vertex $A$. Then for player one's first move, he connects some arbitrary $A$ and $A^\ast$. For the successive moves, either player two connects a pair, or player two doesn't. If player two connects some pair, then player one connects another arbitrary pair (since $\frac{n}{2}$ is odd, player one can always do this if player two can). Otherwise, if player two connected $A$ and $B$, player one connects $A^\ast$ and $B^\ast$. It is not hard to see that this is always a valid move so long as player two's move was valid. So player one will always be able to move if player two did meaning player one wins.
In the case of $n\equiv 0 \pmod 4$, player two employs the same strategy as above except that he assigns the pair so that player one's first move was connecting a pair. So player two wins in this case.
So player one can guarantee a win if and only if $n\equiv 2 \pmod 4$.
jj_ca888
05.07.2020 03:22
Call the first player David, and the second player Jacob. We want to find all $n$ for which David wins. Suppose a move is OK ! if it does not create an odd cycle, and blasphemous otherwise. Claim: Jacob wins if $n$ is odd. Proof: FTSoC suppose not. Then, at some point, all of Jacob's possible moves are blasphemous. However, before Jacob makes the blasphemous move, the graph still has no odd cycles, and is therefore bipartite. Therefore, we can assume that the graph is partitioned into two subgraphs $G_x$ and $G_y$ of sizes $x \neq y$ such that $x + y = n = 2k+1$ for some positive integer $k$. Since Jacob has no more OK ! moves, all $xy$ edges drawn between $G_x$ and $G_y$ are already drawn. One of $x, y$ must be even, so the number of edges in this complete bipartite graph is even. However, this is not possible! Jacob always goes after David, so each time before Jacob moves, the number of edges in the graph is odd, so we have our desired contradiction. $\square$ Now, we struggle for hours because it is not quite clear what to do when $n$ is even. If there are $4m+2$ vertices, then create $2m+1$ disjoint pairs of them. David's first move should be to connect some pair. Each move, the player making the current move can either connect a pair or connect two vertices that are not in a pair. If Jacob decides to connect some pair, then on David's next move he also should connect some pair. If Jacob connects vertices $V, W$ that are not in a pair, then David's next move should be to connect vertices $V', W'$, where $(V, V')$ and $(W, W')$ are pairs. We see that since there are an odd number of pairs, no matter what Jacob does, David has an OK ! move. We make sure that no odd cycles can exist in this process since pairs all have an even number of vertices. Therefore, in this case, David wins. If there are $4m$ vertices, then after David moves, Jacob can "assign the pairs" so that David's original move does not matter. Then, Jacob takes the role of David in the previous case, and therefore Jacob wins. Hence, David wins if and only if the total number of vertices is $2 \pmod 4$, and Jacob wins otherwise. $\blacksquare$ Remark: Canadian combo is very interesting
pad
13.08.2020 12:23
Solved with dantaxyz. We claim the first player wins iff $n \equiv 2 \pmod4$. It is well-known that a graph is bipartite iff there is no odd cycle, so by the condition in the problem, whoever finishes the largest bipartite graph first wins. Hence the final state must be $K_{a,b}$ for some $a+b=n$. Suppose $n$ is odd. Then the number of edges in this is $ab=a(n-a)\equiv 0 \pmod2$ since $n$ is odd. Therefore, the second player finishes making the $K_{a,b}$, and hence the first player loses. Henceforth assume $n$ is even. During play, the graph is always bipartite, so color the vertices red and blue; note that the coloring is forced upto switching everything. Call a graph good if there are an equal number of red and blue vertices. Lemma: Suppose there are two good connected components. Then the graph resulting from connecting them by a single edge is also good. Proof: The number of red and blue vertices is obviously equal in the new graph. To make sure that adding the edge is legal, simply note that we can switch all the colors on one of the graphs based on which two vertices the edge connects. $\blacksquare$ Claim: Assuming optimal play from both player, the final state is guaranteed to be $K_{n/2,n/2}$. Proof: Focus on the isolated vertices. Whenever we add an isolated vertex by connecting it to an existing connected component by an edge, its color is forced. We claim the first player can always end his turn with an even number of isolated vertices. The second player can do the same if at any point the first player stops following the following strategy. If after the move of the second player there are an odd number of isolated vertices remaining, then take one and connect it to some existing connected component and color it accordingly. If after the move of the second player there are an even number of isolated vertices remaining, then connect two of them together. Note that the number of isolated vertices decreases at each step. So the player that follows the strategy can end his turn with 0 isolated vertices remaining. After this, the remaining good connected components will eventually all merge together, staying good at each step due to the lemma. So at the end, there are an equal number of red and blue vertices, which means it ends with $K_{n/2,n/2}$. $\blacksquare$ The number of edges in the final state is then $n^2/4$. This is even for $n\equiv 0 \pmod4$ and odd for $n\equiv 2 \pmod4$. So the second player can win for $n\equiv 0 \pmod4$, and the first can win for $n\equiv 2\pmod4$, as claimed.
The logic of the claim is pretty confusing. Here's why the end position is always $K_{n/2,n/2}$. If the first player always follows the strategy, the end position is $K_{n/2,n/2}$. If at any point the first player stops following the strategy, it means that $n\equiv 2\pmod4$, since if $n\equiv 0 \pmod4$, then optimal play for the first player is to continue the strategy. Since we now know $n\equiv 2 \pmod4$, it means the optimal play for the second player is to now follow the strategy to the end, since he can win.
Writing down the exact formulation of the claim and proving it is the hardest part; the ideas themselves are quite natural. In particular, the logic of why the end position is $K_{n/2,n/2}$ always assuming optimal play is pretty tricky.
Eyed
21.10.2020 03:43
The first player is David, the second is Jacob. Jacob wins for all $n\not\equiv2\mod4$. Observe that the graph's final state is always $K_{a, b}$, so if $n$ is odd, then one of $a,b$ is even, so $ab$ is even which means Jacob always wins for odds. If $n$ is divisible by $4$, I claim it is possible for Jacob to force the graph into $K_{\frac{n}{2}, \frac{n}{2}}$. Let $n = 2k$, and colour $k$ of the points red and $k$ of the points blue. At any point in the game, make sure no edge connects two vertices of the same colour. After Jacob's move, I claim there are an equal number of red and blue points in each connected component, and an even number of points have degree greater than $0$. We prove this by induction. The base case is before the first move: there an equal number of red and blue points and $0$ points with positive degree. Assume after Jacob's move, there is an equal number of red and blue points, and an even number of points with positive degree. If David connects same coloured points in the same component, then he would create a cycle. If he connects same coloured points in different components, we can switch the colours of every point in the next component. If David connects to vertices with degree $0$, it doesn't matter. For all those above cases, Jacob just connects a random red and blue vertex with degree greater than $0$. Finally, if David connects a point with degree $0$ with a vertex, we can connected a vertex of a different colour with a point of degree $0$ (odd number of vertices). All these cases still result in an even number of vertices with positive degree and the same number of red and blue vertices. Thus, in the ending state there are an even number of red and blue vertices, so it is a $K_{\frac{n}{2}, \frac{n}{2}}$ graph, with an even number of edges, implying Jacob wins. If $n\equiv 2\mod 4$, we can do the same thing but allow David to force a victory. The idea is the same: at the end of David's move, make sure there are an even number of vertices with positive degree and the same number of red and blue vertices. Thus, Jacob wins iff $n\not\equiv2\mod4$.
itslumi
24.10.2020 20:15
Solved with Pujnk Let $A$ be the first player and $B$ the second player. We divide the problem in 2 cases. Case1: n-odd Lemma1:.Every bipartite garph has no odd cycle. So here is our motivation for considering it a bipartite graph. Now since $n$-odd we divide our graph in two components $a,b$ such that $a+b=n$, we know that the number of edges is $ab$ so $ab=a(n-a)\equiv 0 \pmod2$,so obviously $B$ will finish making the bipartite graph and eventually $A$ will lose. Case2:, $n$-even. Claim1:Each player can force an even number of isolated vertices after his move. So let say $B$ makes a move and leaves an odd number of isolated vertices.So $A$ can make the following move.Take one isolated vertice and connect with one existed connected component.So $A$ will decreas the number of isolated vertices by 1,now if $B$ will leave an even number of isoleted vertices ,than $A$ need just to connect two isolated vertices, and it means that it decreas by 2 the number of isolated vertices. So at the end the number of isolated vertices will be 0.So , the final state is guaranteed to be $K_{n/2,n/2}$.The number of edges is $n^2/4$. even for $n\equiv 0 \pmod4$ and odd for $n\equiv 2 \pmod4$. So the second player can win for $n\equiv 0 \pmod4$, and the first can win for $n\equiv 2\pmod4$.
SnowPanda
02.11.2020 11:09
The answer is $n \equiv 2 \pmod{4}$.
First, note that the graph must always remain bipartite, and must end at $K_{a, b}$ for some $a + b = n$ (it must be bipartite because there are no odd cycles, and if the two groups don't have all edges between them, then the player could add one such edge).
So then the first player wins if $ab$ is odd and loses when $ab$ is even.
First, if $n$ is odd, then $ab$ will be even no matter what the players do, so then the second player always wins.
So now suppose $n$ is even. At every step, we will have some connected components, and some isolated vertices. The connected components must all be bipartite (and there's only one way to split each component into the two groups).
Call a connected component (with more than $1$ vertex) balanced if its two groups have equal sizes. The main idea is that either player can ensure the connected components are all balanced at the end of all their turns, which means they can force the game to end at $K_{n/2, n/2}$.
Suppose the player who's trying to ensure this is Alice, and the other player is Bob. This is clearly true after Alice's first turn. Now suppose it was true after some turn of Alice.
Then if Bob draws an edge between an isolated vertex and a connected component, which adds it to one of that components' groups, then all the connected components except this one have even size and this has odd size, so since $n$ is even, there is at least one vertex left. Alice adds that vertex to the other group of this connected component. (In particular, the game never ends after Bob's turn at this step.)
Otherwise, if Bob does anything else, this doesn't change the property -- he can either draw an edge inside a connected component (which has no effect on group sizes), draw an edge between two isolated vertices (which creates a new balanced connected component), or draw an edge between two vertices in different components (which joins the components, and then both groups still have equal size).
Now Alice can't be in a position with exactly one isolated vertex (because this number must be even). So if there are at least two she can join them, while otherwise, either she's stuck or anything she does will preserve the property.
So then either player can ensure that the graph ends in $K_{n/2, n/2}$. When $n \equiv 2 \pmod{4}$ the first player does this, while when $n \equiv 0 \pmod{4}$ the second player does.
L567
17.04.2021 14:41
Here's my solution, which is similar to others for $n$ odd, but for even $n$, my strategy is completely different (And I hope it works ) To continue the tradition of the above posts, call the players Jacob and David The answer is that Jacob wins iff $n \equiv 2 \pmod 4$ and David wins otherwise. Claim 1 - David wins when $n$ is odd Proof - Suppose FTSOC that David loses. Then, before David's last turn, the graph must be bipartite $K_{a,b}$ such that all possible edges have already been drawn. But since David goes second, it means that the number of edges $ab$ must be odd. But this means $n = a+b$ is even, which is a contradiction Claim 2 - David wins when $4 | n$ Proof - Let $n = 4k$. Divide the vertices into four groups $A,B,C,D$ and number the vertices in each group from $1$ to $k$ so the vertices are now $a_1, a_2..., a_k, b_1, b_2, ..., b_k, c_1, c_2, ..., c_k, d_1, d_2, ...., d_k$ Now, David just copies Jacob whenever he plays. If Jacob connects $a_ia_j$, then David connects $c_ic_j$ and if Jacob connects an edge in $B$, David does the same thing for $D$. If Jacob draws an edge $a_ib_j$, then David connects $c_id_j$ and so on. Its easy to see that this works, and that David always manages to play without creating an odd cycle, because if it did, then Jacob must have created one the previous move, which is impossible. Claim 3 - Jacob wins when $n \equiv 2 \pmod 4$ Proof - Jacob uses almost the same strategy as David had used when $4 | n$. On his first move, he connects some two edges, call them $e_1e_2$. Then, the remaining edges is divisible by $4$ and so the strategy from above can be used. If David ever connects an edge containing $e_1$, Jacob just copies him and does the same thing with $e_2$ and can ensure that he always manages to not lose. Therefore, Jacob wins if and only if $n \equiv 2 \pmod 4$
tree_3
02.08.2021 08:50
We claim the first person wins iff $n \equiv 2 \pmod{4}.$ First, note that the final state both is bipartite (since no odd cycles) and complete (since no moves can be made), thus it is of the form $K_{a, (n-a)}$, and the first person only wins if there are an odd number of edges, i.e. $a, n-a$ are both odd. This already implies that they lose if $n$ is odd. Clearly, all connected components are bipartite, call a component good if the two parts are the same size (note that the split is uniquely determined because it is connected). If $n \equiv 2 \pmod{4}$, we claim the first person can ensure all components with size greater than $1$ are good after their turn, which implies they win since the final state will be a $K_{\frac{n}{2}, \frac{n}{2}}$. We split into cases based on the second person's move. If both endpoints of the edge are in good components then this preserves all components are still good. If an edge is drawn where neither endpoint is in a good component, then both endpoints are isolated vertexes, and this creates a good component. If an edge is drawn where one endpoint is in a good component and the other is not, call the endpoint which was not $V$. Note that there still must be at least one other isolated vertex $V_1$ (since $n$ is even and before this move all components were good). Connecting $V V_1$ makes all components good as desired. On the other hand, if $n \equiv 0 \pmod{4}$, the second person can use the same strategy and also ensure that the ending state is $K_{\frac{n}{2}, \frac{n}{2}}$, guaranteeing the first person loses as desired.
bora_olmez
03.04.2022 22:48
I got bored while writing my economics essay, this is the same solution as others, except, in order to keep things original, I will prove that each graph with no odd cycles is bipartite as well (which is not complicated at all). $\textbf{Lemma 1:}$ Each graph simple graph $G(V,E)$ with no odd cycles is bipartite. $\textbf{Proof)}$ We will prove the result for connected graphs, for any graph with multiple connected components, we can simply pick one of the two sets creating the two-coloring for each of the connected components and put them together which creates a 2-coloring of the graph. Assume for the sake of contradiction that $G$ has no odd cycles and is not two-colorable. Now, we know that $G$ has a spanning tree (it is connected), two-color it in the unique way and notice that if there are two vertices $v_1$ and $v_2$ that are adjacent but of different color, the path connecting $v_1, v_2$ in the spanning-tree along with the edge $\{v_1, v_2\}$ form an odd cycle which is a contradiction. $\blacksquare$ Call the first player $A$ and the second player $B$, we claim that $A$ can only win if $n \equiv 2 \pmod{4}$. $\textbf{Lemma 2:}$ The graph is $K_{a,b}$ for some $a+b = n$ when the final move occurs. $\textbf{Proof)}$ This is simply because after the final move occurs, the graph should be bipartite by $\textbf{Lemma 1}$ and there should be no missing edges, hence it should be a complete bipartite graph. $\blacksquare$ $\textbf{Lemma 3:}$ $B$ wins if $n$ is odd $\textbf{Proof)}$ In fact, as long as player $B$ plays any move that creates no odd cycles if he has such a move, he can win. This is because $K_{a,b}$ has $ab \equiv 0 \pmod{2}$ edges because $a+b \equiv 1 \pmod{2}$ means that one of the two components of the complete bipartite graph will have an even number of edges. $\blacksquare$ Now, let a marriage-like bipartite graph be one such that both components have an equal number of vertices (with at least $2$ vertices), the following Lemma solves the rest of the problem. Assume also that $n$ is even by $\textbf{Lemma 3}$. $\textbf{Lemma 4:}$ If $n \geq 4$, both $A$ and $B$ are able to ensure that after their move, the graph is a disjoint union of marriage-like bipartite graphs and an even number of isolated vertices unless the graph is already a complete bipartite graph. $\textbf{Proof)}$ Let $C$ be the player who wants to keep the graph marriage-like and $D$ be the other player. Assume that $D$ makes a move on a graph which is a disjoint union of marriage-like bipartite graphs and an even number of isolated vertices, if $D$ connected a marriage-like bipartite graph to an isolated vertex, there is another isolated vertex in the graph which $C$ may connect with $D$ which keeps the number of isolated vertices even while maintaining the marriage-like bipartite graph. If $D$ connects two marriage-like bipartite graphs, the union of the two marriage-like bipartite graphs is not yet complete and hence $C$ may add an edge within the new marriage-like bipartite graph. Finally, if $D$ connects two isolated vertices, there are either another pair of isolated vertices which $C$ may connect or because $n \geq 4$ there is a marriage-like bipartite graph which $C$ may add the two vertices to. This exhausts all possible cases because we know that any connected component was either a marriage-like bipartite graph or an isolated vertex. $\blacksquare$ $\textbf{Lemma 5}$ $A$ wins if $n \equiv 2 \pmod{4}$ and $B$ wins if $n \equiv 0 \pmod{4}$ $\textbf{Proof)}$ This is an immediate corollary of $\textbf{Lemma 4}$, notice that if $n \equiv 2 \pmod{4}$, player $A$ can ensure that after his move the graph is a disjoint union of marriage-like bipartite graphs, and isolated vertices and hence, the graph will eventually become $K_{\frac{n}{2}, \frac{n}{2}}$ which has an odd number of edges and when $B$ moves, he will lose, otherwise $n \equiv 0 \pmod{4}$ for which $B$ ensures that the graph reaches $K_{\frac{n}{2},\frac{n}{2}}$ as its end state which has an even number of edges and in the next move $A$ loses. $\blacksquare$
IAmTheHazard
27.05.2022 16:53
Very nice. Call the first player David and the second Jacob. David can win if and only if $n \equiv 2 \pmod{4}$. Note that any connected graph only has a single \say{bipartite partition} up to swapping the subgraphs. Now consider the state of the graph right before losing under optimal play. Obviously, it must be connected (else the player could just connect the graph and continue on), and bipartite (else the game would be over already). If the unique bipartite partition of this connected graph is into $x$ and $y$ vertices where $x+y=n$, then the losing edge is the $xy+1$-th as there are $xy$ edges in the complete bipartite graph. For $n$ odd, $xy$ is always even no matter what, so David will always place the losing $xy+1$-th edge. If $n \equiv 0 \pmod{4}$, then Jacob can win by employing the following strategy, which inductively guarantees that the unique bipartite partition of any connected component in $G$ splits it into equally sized subgraphs (i.e. same # of vertices), unless that connected component is a singleton, and that there are an even number of singletons after Jacob's move, until $G$ is connected (phew). First, after David's first move connecting two singletons in $G$, Jacob connects two different singletons in $G$, leaving $n-4$ singletons. At this point, the condition is met. Now, if the condition is satisfied and David \say{joins} two connected components, which are either both singletons or both not singletons, by drawing an edge between them, the condition is still satisfied. In this case, Jacob can make a similar move joining two connected components, since there can never be an odd number of singletons left—if he cannot do this, then $G$ is connected as it only has one connected component. Otherwise, if David joins a singleton to a part $A$ of non-singleton $C=A \cup B$, then there are an odd number of singletons left, so Jacob may join another singleton to part $B$, which preserves the truth of the hypothesis. Then, when $G$ becomes fully connected, it's bipartite partition is into parts of size $n/2$, which is even. Then $(n/2)^2$ is even as well, so David will always place the losing $(n/2)^2+1$-th edge. For $n \equiv 2 \pmod{4}$, David can win with a similar strategy. If Jacob joins a singleton to part $A$ of non-singleton $C=A \cup B$, then David joins a singleton to part $B$, which he can guarantee always exists on his turn. Otherwise, he just arbitrarily connects either two singletons or two non-singletons. The end result, once $G$ is connected, is also that the partition of $G$ is into parts of size $n/2$, which is odd. Then $(n/2)^2$ is odd as well, so Jacob places the losing $(n/2)^2+1$-th edge. $\blacksquare$
blackbluecar
12.02.2023 01:22
Let the players be David and Jacob with David going first. We claim David can win iff $n \equiv 2 \pmod{4}$ First, consider $n = 4k$. Jacob can win by the following strategy. Partition $G$ into two sets of vertices $A = \{a_1, a_2, \ldots, a_{2k} \}$ and $B = \{b_1,b_2, \ldots, b_{2k} \}$ of equal sizes. -If David connects $a_i$ to $a_j$ then Jacob connects $b_i$ and $b_j$. -If David connects $b_i$ to $b_j$ then Jacob connects $a_i$ and $a_j$. -If David connects $a_i$ to $b_j$ where $i \not = j$ then Jacob connects $b_i$ and $a_j$ -If David connects $a_i$ to $b_i$ then Jacob connects $a_j$ and $b_j$ for an arbitrary choice of $j$. What this does is creates two graphs $A$ and $B$ which are exactly identical. David is forced to make the first move that makes an odd cycle. For $n = 4k+2$ David can will by the previous strategy but with the starting move connecting $a_1$ to $b_1$. Now, assume $n$ is odd. For now on, color the graph. Notice that whoever makes the chromatic number of the graph $\geq 3$ loses. Jacob now has a winning strategy. He will play according to the following rules. -If David connects two connected components and creates a new connected component $C$, Jacob connects another connected component to $C$ to make the new connected component of odd size. -If David connects two vertices within the same connected component, David will do the same. First, we will show that the first rule guarantees that all connected components have odd sizes at the start of Davids's turn every round. Indeed, we will prove this by induction. Notice that initially, every vertex is a unique connected component of size $1$. Now, assume that David connects two connected components, and the resulting component will have an even size. So, Jacob connects another component of odd size to the new component, resulting in every component having an odd size. But, if every connected component has odd size, there are always an even number of edges that maintain the two colorings. Thus, Jacob will win on parity. $\blacksquare$
vsamc
29.06.2023 05:19
Probably my favorite problem in DCX-graph <3
If $n$ is odd or $4\mid n$, Jacob has a winning strategy. Else, if $n\equiv 2\pmod{4}$, then David has a winning strategy.
If $n$ is odd, then Jacob should do the following: on his move, note that there are no odd cycles, so at that point $G$ is bipartite. Let $G = A\cup B$ be a bipartition of $G$. Then, note that the number of edges in a complete bipartite graph $K_{|A|, |B|}$ is $|A|\cdot |B| = |A|(n-|A|)$. Since $n$ is odd, it follows that $|A|(n-|A|)$ is even, since at least one of $|A|, n-|A|$ is even. However, whenever it's Jacob's turn (right before it), the number of edges in $G$ is odd. Thus, the graph is not $K_{|A|, |B|}$, so Jacob can still add an edge from some $a\in A$ to some $b\in B$ that has not already been drawn, keeping $G$ bipartite and therefore keeping $G$ to having no odd cycles. Jacob can always do this on his turn, so he will not be the one who makes the odd cycle and so he will win with this strategy since the number of edges is monovariant so the game will eventually end, and he will win regardless of what David does.
If $n \equiv 2\pmod{4}$, then David should first do the following: On his first turn, he can choose a random edge, and call the endpoints $v_1$ and $v_2$. Then, if Jacob draws an edge from $v_1$ or $v_2$ to another vertex, call the other vertex $v_3$, and David should draw an edge from $v_3$ to another vertex not in $\{v_1, v_2, v_3\}$, and call this vertex $v_4$. Else, Jacob draws an edge from two other vertices, call them $v_3$ and $v_4$. Then, David should draw an edge from two other vertices $v_5$ and $v_6$ not in $\{v_1, v_2, v_3, v_4\}$. At this point, there are an even number of points in $G$ have degree at least $1$, and they are in "pairs" $(v_{2i-1}, v_{2i})$. David's primary objective now should be to make sure that this will always be the case, and that he adds at least $2$ vertices each time to the set of vertices of degree at least $1$, so that at one point, all vertices will have degree at least $1$ and they are in disjoint pairs $(v_{2i-1}, v_{2i})$, where the vertices in each pair are connected to each other.
So, until we have this ideal scenario where all vertices have degree at least $1$ are in disjoint pairs, David should do the following: Suppose that after David's move, he has managed to make the set of vertices in $G$ with degree at least $1$ as $V = \{v_1, v_2, \cdots, v_{2r-1}, v_{2r}\}$ for some $r < \tfrac{n}{2}$, such that $v_{2i-1}$ is connected to $v_{2i}$ for all $1\leq i\leq r$. Then, we have a few cases.
If Jacob connects two vertices of $V$, and makes an odd cycle, then he loses, so assume he does not make an odd cycle by doing so. Then, the set of all vertices in $G$ with degree at least $1$ is unchanged. Then, David can connect two vertices $v_{2r+1}$ and $v_{2r+2}$ which are not in $V$ (since $r < \tfrac{n}{2}$), and $V$ is now $\{v_1, v_2, \cdots, v_{2r+2}\}$, and $v_{2i-1}$ is connected to $v_{2i}$ for all $1\leq i\leq r+1$, so we have managed to make $V$ still of the same form and increase $|V|$ by $2$.
If Jacob connects one vertices of $V$ to another element not in $V$, say $v_i$ for some $1\leq i\leq 2r$ to another vertex, say $v_{2r+1}$ not in $V$, then if Jacob does not immediately lose, David should connect $v_{2r+1}$ to yet another vertex $v_{2r+2}$ not equal to any of the previous vertices. Note that David does not make an odd cycle since such a cycle must have included the edge from $v_{2r+1}$ to $v_{2r+2}$, but $\deg v_{2r+2} = 1 < 2$, so $v_{2r+2}$ cannot be part of an odd cycle. Now, $V = \{v_1, v_2, \cdots, v_{2r+2}\}$, and $v_{2i-1}$ is connected to $v_{2i}$ for all $1\leq i\leq r+1$, so we have managed to make $V$ still of the same form and increase $|V|$ by $2$.
If Jacob connects two distinct elements $v_{2r+1}$ and $v_{2r+2}$ not in $V$ (which obviously does not create an odd cycle), then if $r = \tfrac{n}{2}-1$, then we have our desired scenario, so David should refer to the instructions for that section if this occurs. Else, we have that $r\leq \tfrac{n}{2}-2$, so there exists vertices $v_{2r+3}$ and $v_{2r+4}$ not in $V$, so David should connect them (and this obviously does not create an odd cycle). Then, $V = \{v_1, v_2, \cdots, v_{2r+4}\}$, and $v_{2i-1}$ is connected to $v_{2i}$ for all $1\leq i\leq r+2$, so we have managed to make $V$ still of the same form and increase $|V|$ by $4$.
Thus, in all cases, David can do what we claimed. Thus, after a sufficiently large amount of moves, either Jacob loses in the midst of David's algorithm or we have that all vertices $v_1, v_2, \cdots, v_{n}$ have degree at least $1$, and $v_{2i-1}, v_{2i}$ are connected for all $1\leq i\leq \tfrac{n}{2}$. Then, on David's turn, we have that $G$ has no odd cycles, so $G$ is bipartite. However, since $v_{2i-1}$ and $v_{2i}$ are connected, they are of opposing colors. Thus, if $G = A\cup B$ is a bipartition of $G$, we have that one of $\{v_{2i-1}, v_{2i}\}$ is in $A$, and the other one is in $B$, for all $1\leq i\leq \tfrac{n}{2}$. Then, it follows that $|A| = |B| = \tfrac{n}{2}$, since $|A| \geq \tfrac{n}{2}$, $|B| \geq \tfrac{n}{2}$, and $|A|+|B| = |G| = n$. Thus, the complete bipartite graph $K_{|A|, |B|}$ has $\left(\frac{n}{2}\right)^2$ edges. Since $n\equiv 2\pmod{4}$, $\frac{n}{2}$ is odd, so $\left(\frac{n}{2}\right)^2 = \frac{n^2}{4}$ is odd as well. However, note that on David's turn (right before it), the number of edges is even. Thus, $G$ is not $K_{|A|, |B|}$, so David can connect an $a\in A$ and a $b\in B$ which are not already connected, keeping $G$ bipartite and so keeping it devoid of an odd cycle. David can keep doing this, so he will not be the one who first creates an odd cycle and so he will win with this strategy since the number of edges is monovariant so the game will eventually end, and he will win regardless of what Jacob does.
If $4 \mid n$, then if David connects two vertices $v_1$ and $v_2$, then Jacob should connect two vertices $v_3$ and $v_4$ not in $\{v_1, v_2\}$, and then employ the same exact strategy that David employs in the $n\equiv 2\pmod{4}$ case to get to a point where after a sufficiently large number of moves, either David lost along the way, or $V = \{v_1, v_2, \cdots, v_{n}\}$, and $v_{2i-1}$ is connected to $v_{2i}$ for all $1\leq i\leq \tfrac{n}{2}$. Then, suppose it was David's move. Then, $G$ has no odd cycles, so it is bipartite, so let $G = A\cup B$ be a bipartition of $G$. Then, by the same logic as the $n\equiv 2\pmod{4}$ case for David, we have that $|A| = |B| = \tfrac{n}{2}$, and $K_{|A|, |B|}$ has $\left(\frac{n}{2}\right)^2$ edges. Since $4\mid n$, $\frac{n}{2}$ is even, so $\left(\frac{n}{2}\right)^2$ is even as well. However, on Jacob's turn (right before it), the number of edges drawn is always odd. Thus, $G$ is not $K_{|A|, |B|}$, so Jacob can connect an $a\in A$ and a $b\in B$ which are not already connected, keeping $G$ bipartite and so keeping it devoid of an odd cycle. Jacob can keep doing this, so he will not be the one who first creates an odd cycle and so he will win with this strategy since the number of edges is monovariant so the game will eventually end, and he will win regardless of what David does. $\blacksquare$
HamstPan38825
03.09.2023 19:14
Very fun problem to do David wins if and only if $n \equiv 2 \pmod 4$. First, if $n$ is odd, then notice that immediately before the game ends, the graph must be bipartite. Thus, it has an even number of edges, which means that Jacob necessarily wins. If $n$ is even, consider a $2$-coloring on the graph $G$. Color the first two vertices connected red and blue, and for any vertex added onto a connected component, color it the corresponding color. If the new edge is part of a different connected component, color them red and blue arbitrarily; this will not end up mattering, as we will see. The the key claim is the following: Claim. For each even $n = 2k$, both Jacob and David can guarantee (depending on the value of $n$) that the number of red and blue vertices in every connected component after every vertex is colored is equal. Proof. Check the base cases manually. We consider the claim from the perspective of Jacob; the other perspective is identical. Suppose that after $k$ moves by each player (thus $2k$ edges), Jacob has guaranteed that the number of vertices of each color in every component is equal. Then, if David attaches a red vertex to an existing blue vertex, Jacob can do the exact opposite in the same component; if David introduces a new connected component, Jacob can also introduce one, which will satisfy the claim regardless of the coloring of that component. $\blacksquare$ It follows that for $n = 4k+2$, David can guarantee that there are $2k+1$ vertices of each color. On the other hand, if Jacob attempts to connect two identically colored vertices in two different components, we can simply flip the colors of the vertices in one component, which will not change the number of vertices of each color. Thus, $(2k+1)^2$ edges can be connected at most, so David wins. Similarly, Jacob wins in the case $n=4k$.
thdnder
13.09.2023 12:37
It's similar to others, but I'll post it. If $n \equiv 2 (4)$, then David wins, otherwise Jacob wins. Observe the final state of graph is a complete bipartite graph $K_{a,b}$ with $a + b = n$. So if $n$ odd. This means that David wins if only if $a, b$ are both odd. So $n$ is odd, then Jacob wins. Now assume $n$ is even. Consider the case $n \equiv 2 (4)$. Then we claim that David can force the final state $K_{\frac{n}{2}, \frac{n}{2}}$. Color the vertices of $G$ 2 colors, namely 0,1 such that adjacent 2 vertices have different colors. We prove that in after David's move, number of 0 vertices are equal to number of 1 vertices. It's enough to prove that after $k$th David move, number of 0 vertices are equal to number of 1 vertices. Induct on $k$. Base case is trivial. Now assume that after $k-1$th David move, number of 0 vertices are equal to number of 1 vertices. Then after Jacob moves, the difference between number of 1 vertices and number of 0 vertices are most 1. If the above difference is 0, then David chooses two vertices that hasn't chosen. If the difference is 1, WLOG assume number of 0 vertices are less than number of 1 vertices. Then David chooses two vertices that one of these are colored 1 and the other one isn't colored yet. (Since the number of vertices that are colored is odd and the number of all vertices is even, we can choose the vertex that isn't colored) So if $n \equiv 2 (4)$, then the final state of $G$ is $K_{\frac{n}{2}, \frac{n}{2}}$. Thus game ends after $(\frac{n}{2})^2$ moves. So David wins in this case. If $n \equiv 0 (4)$, then similarly Jacob can force the final state $K_{\frac{n}{2}, \frac{n}{2}}$. So David wins if and only if $n \equiv 2 (4)$, so we're done. $\blacksquare$
kamatadu
01.01.2024 21:37
If (i) $n$ is odd $\implies$ Jacob wins, (ii) $n = 4k \implies$ Jacob wins, (iii) $n=4k+2\implies$ David wins. If $n$ is odd, then at the last move, we arrive at some $K_{a,b}$ where $a+b = n$. So there were $a\times b$ moves at the end which is even. So the last move was Jacob's. If $n = 4k+2$, David initially $2$ empty sets $A$ and $B$. David draws an edge and pushes one of the vertices into $A$ and the other into $B$. Now if Jacob draws an edge that is disconnected and if $|A|,|B| \neq \dfrac{n}{2}$, David also creates a disconnected edge and pushes one of its vertices in $A$ and $B$. DAvid pushes Jacob's edge's vertices into $A$ and $B$ too. If Jacob gives a move that has an edge with one vertex in WLOG $A$ and the other one neither in $A$ or $B$, then DAvid copies Jacob's move and gives a move with a vertex from set $B$ which corresponds to the vertex in $A$ from which Jacob gave his move. If Jacob connects a vertex from $A$ to $B$, then David just gives a new disconnected edge. Basically we are making both sets symmetric. So at the end, we have $|A|=|B| = \dfrac{n}{2}$. So we end up with $K_{\frac{n}{2},\frac{n}{2}}$. This has odd edges and so David wins. For $n=4k$, Jacob follows the same strategy as David used for $n=4k$. For his initial move, Jacob gives move on two new vertices neither in $A$ or $B$. We end up with $K_{\frac{n}{2},\frac{n}{2}}$ which has even edges and so, Jacob wins.
megarnie
19.01.2024 01:25
Let David play first and Jacob play second. The answer is David wins iff $n\equiv 2\pmod 4 $ and Jacob wins iff $n \equiv 0,1,3\pmod 4$. The state right before the final move must be a $K_{a,b}$ for some $a,b$ with $ a+b=n$, so it must have $ab$ edges. If $n$ is odd, then $ab$ is even, so it must be David's turn which means Jacob wins. Now assume $n$ is even. We prove that either player can make the graph into a $K_{n/2, n/2}$. Consider a coloring of the non-isolated vertices into two colors, red and blue where no two adjacent vertices have the same color, and we add a color to a vertex once it gets connected to an edge. Such a coloring has to exist (otherwise there would be an odd cycle), and is unique up to the choice of the first vertex's color (WLOG it is blue). We show that either player can ensure there are the same number of red and blue vertices at any point after their turn and before an odd cycle or a $K_{n/2,n/2}$ is created. If the person before made a move connecting either two isolated vertices or no isolated vertices, then the graph still has the same number of blue and red vertices. Since the graph isn't a $K_{n/2,n/2}$, there are either two vertices of different colors not connected yet or two isolated vertices, which means we can either connect those two vertices of different colors or those two isolated vertices, and this makes sure the graph has the same number of blue and red vertices. If the person before made a move connecting one isolated vertex with a non-isolated vertex, then we can connect another isolated vertex (must exist since prior to the other person's turn, there were an even number of isolated vertices) with a non-isolated vertex of the other color. This clearly increases the number of vertices of each color by $1$, so there still will be the same number of blue and red vertices. This implies that if both players play optimally (i.e. no one forms an odd cycle unless they have to), either player can force the graph to become a $K_{n/2,n/2}$ (since any other $K_{a,b}$ doesn't have the same number of blue and red vertices. So if $n = 4k$, Jacob can force it into a $K_{2k,2k}$ after an even number of moves, which means David is forced to create an odd cycle, so Jacob wins. If $n = 4k + 2$, then David can force it into a $K_{2k+1,2k+1}$ after an odd number of moves, which means that Jacob is forced to make an odd cycle, so David wins.
Kappa_Beta_725
12.11.2024 08:59
Let David play first and Jacob play second. I once again have a short solution: Claim: David wins iff $n \equiv 2 \pmod 4$ Proof: The move before one of the players play a losing move, the graph must have been a bipartite graph. If $n$ is odd, one of the partite sets of the graph must have an even number of vertices. In this case players keep making moves till the bipartite graph becomes a complete bipartite graph which takes even steps (Hence Jacob wins). If $n$ is $2\pmod 4$ David tries to make a bipartite with the two partite sets have size equal to $\frac n 2 \equiv 1 \pmod 2$. He can always do this. David starts off by connecting any two random vertices and follows the following strategy afterwards: If Jacob makes a move connecting two vertices which were disconnected from the graph, David does the same. If Jacob makes a move connecting a vertex which is connected to the graph to a vertex which is not, David connects the latter vertex to a vertex which is not connected to the graph. Finally, if Jacob connects two connected vertices, David connects two vertices which were disconnected. This process keeps on going until a connected graph has been reached. Observe that there are $\frac n 2$ edges connecting $2 \times \frac n 2$ distinct vertices which implies that the two partite sets have size $\frac n 2$ If $n\equiv 0 \pmod 4$, Jacob follows a similar strategy and wins. $\blacksquare$
N3bula
09.12.2024 01:34
When $n$ is odd Jacob wins. Clearly if $n$ is odd in any bipartite graph on $n$ vertices it has an even number of edges, as Jacon can always play as to keep the graph bipartite and if David makes a move that does not do that he loses Jacob can always win. If $n$ is $0\pmod 4$, Jacob can also win. He does this by playing symetrically to David, if we have a number of connected components such that each component has an equal distribution of colour 1 vs colour 2 when they are 2 coloured, suppose Jacob makes a move in this position, he either adds an amount $1\pmod 2$ or $0\pmod 2$ to one of the connected components or creates a new connected component with everything equal. David can always respond such that he makes the connected component that is now unbalanced balanced or creating a new connected component or if all vertices are in components he is guaranteed to win. When $n$ is $2\pmod 4$ Jacob can use a similar strategy to win.