, 2017

Solution:

Let $n$ denote the number of teams.

Lemma: Given a connected graph $G$, the imbalance of $G$ is 1 iff $G$ is a tree. Let's just talk in terms of directed graphs and indegree/outdegree.

Proof. If there is a cycle, direct the cycle such that it is a directed cycle. Then from this cycle, point all remaining edges outwards. If $G$ is a tree, induct on the size. Take any leaf. If it wins its game, it is undefeated. Otherwise, it must lose to its neighbor. Then induct on the tree resulting after deleting the leaf.

Now the finish is a simple counting argument using expected values. Using Cayley's formula, for each subset of vertices, we compute the probability that it is a maximal connected component and is a tree. This ends up being
$$2^{-\binom{n}{2}} \sum_{i=1}^{n}\binom{n}{i} \cdot i^{i-2} \cdot 2^{\binom{n-i}{2}} .$$
This evaluates to $\frac{5055}{2^{15}}$ for $n=6$.