Adithya and Bill are playing a game on a connected graph with $n > 2$ vertices, two of which are labeled $A$ and $B$, so that $A$ and $B$ are distinct and non-adjacent and known to both players. Adithya starts on vertex $A$ and Bill starts on $B$. Each turn, both players move simultaneously: Bill moves to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay at his current vertex. Adithya loses if he is on the same vertex as Bill, and wins if he reaches $B$ alone. Adithya cannot see where Bill is, but Bill can see where Adithya is. Given that Adithya has a winning strategy, what is the maximum possible number of edges the graph may have? (Your answer may be in terms of $n$.) Proposed by Steven Liu
Problem
Source: 2019 ELMO Shortlist C2
Tags: combinatorics, graph theory, Combinatorial games, game
28.06.2019 15:36
05.10.2020 13:07
Redacted
05.10.2020 13:59
Afo wrote: After giving a construction, can't we just say that it's trivial that the degree of $B$ is at most $1$ You can of course say this, but it is neither trivial nor true: On the 4-cycle $A-x-B-y-A$, Adithya does have a winning strategy and the number of edges is $4={4-1\choose2}+1$. However, the degree of $B$ is NOT at most $1$.
05.10.2020 15:24
Redacted
05.10.2020 15:42
This problem is so cute,love it. So here is my solution(anyway very similar to #2) First we guess that the answer is $\boxed{\binom{n-1}{2} + 1}.$,We have 2 main claims that will help us solve the problem $Calim 1.$. $B$ will always win if $B$ can form a triangle connecting his vertex and 2 other connected vertices. $Proof$ ;Since B can see where $A$ will be ,then using his starting vertice $B$ and the other two connected ones with $B$ (to forme a triangle),at which time he wants he can be at any positions he wants,(in these 3 points that forms a triangle),so basicly $A$ will never win. $Claim 2.$. ,Let us take $n-1$ vertixes appart from $B$,and take an edge between every pair of them.Let $B$ be connected to a vertex $C$ ,from $Claim .1.$ we know that $B$ can not be connected to any other vertex other than $C$,so $A$ will make the following move to guarantee that he will win. $A-->A-->C-->B$ ,since $B$ is always in the move ,he can never get to his starting positions in 3 moves,and $A$ will always win from this confiraguration. From $Claim 2$ we get that $\binom{n-1}{2} + 1$,also from $Claim 1.$ we get that since no two of these $k$ vertixes may be connected with each other (otherwise A will lose) we get that $\binom{n-1}{2} - \binom{k}{2}$ edges appart from $B$ can be made. Thus, we get the upper bound $k + \binom{n-1}{2} - \binom{k}{2} = \binom{n-1}{2} - \frac{k^2 - 3k}{2} \leq \binom{n-1}{2} + 1,$ $\blacksquare$
20.07.2021 08:54
Redoing it, since the previous one is a fake-solve. Solution. The answer is $\binom{n-1}{2}+1$. The construction is to make a complete graph out of all vertices except $B$ and add an edge between $B$ to any other vertex $\neq A$. This is possible since $n \ge 3$. Claim 1. There is no triangle containing $B$ Proof. If there is, Bill can go to $B$ in the $i^{th}$ move for any $i=2,3,\dots$. $\blacksquare$ Let there be exactly $k$ vertices adjacent to $B$. The graph contains at most $\binom{n}{2}$ edges. However, it is necessary that the $k$ vertices are not adjacent to one another by Claim 1. It's also necessary that the other $n - k - 1$ vertices (The vertices that are not adjacent to $B$ or is $B$ itself) can't be adjacent to $B$. So the graph contains at most $\binom{n}{2} -\binom{k}{2} - (n-k-1)$ edges. We finish the problem by showing $$\binom{n}{2} -\binom{k}{2} - (n-k-1) \leq \binom{n-1}{2}+1$$$$\iff (k-1)(k-2) \ge 0$$ Remark. This is the same as the other solutions since $$\binom{n}{2} -\binom{k}{2} - (n-k-1) = k + \binom{n-1}{2} - \binom{k}{2}$$
29.08.2021 23:20
Let a reverse edge be an unordered pair of vertices that aren't connected. We claim the minimum number of reverse edges is $n-2$. The construction for $n-2$ reverse edges is a $K_{n-1}$ with a leaf. Let the leaf be $VB$ where $B$ has degree $1$. Adithya's strategy is simply to stay at $A$, move to $V$, then move to $B$, which clearly works. Lemma: In a graph on $n$ vertices with at most $n-3$ reverse edges, every vertex is part of a triangle. Proof: Suppose, towards contradiction, that a vertex $V$ of degree $k$ is not part of a triangle. Then the graph has at least $n - 1 - k + \binom{k}{2}\ge n - 1 - k + (k-1) = n-2$ reverse edges, a contradiction and the lemma is established. By the lemma, we know that $B$ is part of a triangle. In particular, Bill can reach $B$ again in $2$ moves or $3$ moves, and hence $m$ moves for all $m\ge 2$ by induction. Since $A$ and $B$ are not adjacent this means Adithya cannot possibly have a winning strategy, as desired.