A game on a graph

Question

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses a positive integer number $m,\: 1\leq m \leq 1000$ and after that directs $m$ undirected edges of $G$. The game ends when all edges are directed. If there is some directed cycle in $G$ Alice wins. Determine whether Alice has a winning strategy.

This problem is from the Turkey JBMO TST 2014. Could someone help? I have not gone anywhere with it. Thanks a lot.

Answer 1

This is not a full solution, but this may help:

The name of the structure we get at the end is tournament.

A transitive tournament is one where $a\to b$ and $b\to c$ implies $a\to c$, thus they give us a total ordering of the vertices.

Tournaments are only acyclic if they are transitive, in particular a tournament $T$ has no $3$-cycle if and only if it is transitive. Notice a transitive graph has no cycles. Now suppose a graph is not transitive, then there exists $a,b,c$ such that $a\to b, b\to c$ and $c\to a$.

So If Bob wants to win he has to build a transitive graph. Notice any tournament with outdegree sequence $(0,1,2\dots ,n-1)$ is transitive. Can Bob build this graph?

Answer 2

A sketch showing Alice can win. Alice makes a directed chain, extending it by one step (or two if there is a stray edge she can use) at each turn. When the chain has $n$ steps, Bob needs to have directed a total of $\frac 12(n)(n-1)$ edges or Alice can win the next time. We therefore need $\frac 12(n)(n-1) \gt 1000n$, which happens at $n=2001$, so Alice can win by the $2004$th turn

Added: When Alice's chain is 2 edges long, there is only one edge that can complete a cycle. Bob has to orient that one the wrong way to prevent Alice winning on the next move. When her chain is $n=4$ edges long, there are $\frac 12(4-1)(4-2)=6$ edges that could win- three from the head end of the chain, to from the next point down, and one from the next to bottom, so Bob has to orient all $6$ of these by his third turn. As Alice's chain gets longer, the number of edges Bob has to orient grows quadratically. The number of edges Bob can orient only grows linearly, so eventually (unless she runs out of points) she will win.

Answer 3

Alice has the winning strategy. We first prove that on each of her turns, if the length of the longest directed chain isn't already $2014$, Alice can always extend it by one. We then use this to give an explicit winning strategy.

To prove our lemma, suppose otherwise. Let $(v_1, v_2, \ldots, v_n)$ be the longest directed chain as of yet, and let $S\neq\varnothing$ be the set of vertices not on the chain. Every single point of $S$ must point to $v_n$ – otherwise, the chain could be trivially extended by Alice. Let $i<n$ be the least integer such that not every single point of $S$ points to $v_i$. Let $a\in S$ such that $a$ does not point to $v_i$. Alice can then connect $v_i$ to $a$, thus creating the new longest chain $(v_1, \ldots, v_i, a, v_{i+1}, \ldots, v_n)$, as we wanted to prove.

Alice thus has the following winning strategy. She builds an ever-increasing chain by the method above. By turn $n=2002$, Alice will have created a chain of length at least $2002$. Since $\binom{2002}{2}>1000\cdot2002$, after Bob's turn, two vertices of the chain will remain unconnected. Alice can then form a cycle with them. $\blacksquare$