HMMT 2018 T8

Allen plays a game on a tree with $2 n$ vertices, each of whose vertices can be red or blue. Initially, all of the vertices of the tree are colored red. In one move, Allen is allowed to take two vertices of the same color which are connected by an edge and change both of them to the opposite color. He wins if at any time, all of the vertices of the tree are colored blue. (a) (20) Show that Allen can win if and only if the vertices can be split up into two groups $V_{1}$ and $V_{2}$ of size $n$, such that each edge in the tree has one endpoint in $V_{1}$ and one endpoint in $V_{2}$. (b) (40) Let $V_{1}=\left\{a_{1}, \ldots, a_{n}\right\}$ and $V_{2}=\left\{b_{1}, \ldots, b_{n}\right\}$ from part (a). Let $M$ be the minimum over all permutations $\sigma$ of $\{1, \ldots, n\}$ of the quantity

$$\sum_{i=1}^{n} d\left(a_{i}, b_{\sigma(i)}\right)$$

where $d(v, w)$ denotes the number of edges along the shortest path between vertices $v$ and $w$ in the tree. Show that if Allen can win, then the minimum number of moves that it can take for Allen to win is equal to $M$. (A graph consists of a set of vertices and some edges between distinct pairs of vertices. It is connected if every pair of vertices are connected by some path of one or more edges. A tree is a graph which is connected, in which the number of edges is one less than the number of vertices.)