Team Selection Test for IMO 2011

We want to find the largest integer $k$ such that a directed path exists from any vertex $v_1$ to any vertex $v_2$ in any directed complete graph $G$ with 2011 vertices satisfying $|\text{indeg}(v)-\text{outdeg}(v)|\le k$ for all vertices $v$. The answer is 1005.

Observe that $|\text{indeg}(v)-\text{outdeg}(v)|$ is always even. We first give a counterexample with $k=1006$. Let $V=X\cup Y$, $X=\{x_1,x_2,\dots ,x_{1005}\}$, $Y=\{y_1,y_2,\dots ,y_{1006}\}$, and $E=\{(x_i,x_j):1\le i<j\le \max (i+502,1005)\text{ or }1\le j\le \max (i-503,0)\}\cup \{(y_i,y_j):1\le i<j\le \max (i+503,1006)\text{ or }1\le j<\max (i-503,0)\}\cup \{(x_i,y_j):1\le i\le 1005\text{ and }1\le j\le 1006\}$.

Then $|\text{indeg}(v)-\text{outdeg}(v)|\le 1006$ for all $v\in V$ in the graph $G=(V,E)$, but there is no directed path from $y_1$ to $x_1$.

Now we will show that there is a directed path from any vertex to any vertex if $|\text{indeg}(v)-\text{outdeg}(v)|\le 1004$ for all vertices $v$. Note that if one of $\text{indeg}(v)$ and $\text{outdeg}(v)$ is less than 503, then the other is greater than 1507 and $|\text{indeg}(v)-\text{outdeg}(v)|$ is at least 1006. Therefore $\text{indeg}(v)$ and $\text{outdeg}(v)$ are both at least 503.

Let $v_1$ and $v_2$ be two distinct vertices in $G$. Let $V_1$ be the set of vertices that can be reached from $v_1$ and let $V_2$ be the set of vertices from which $v_2$ can be reached. Then all arrows with tail in $V_1$ have also their heads in $V_1$. Therefore the sum of $\text{outdeg}(v)$ for $v$ in $V_1$ is $\left(\genfrac{}{}{0ex}{}{|V_1|}{2}\right)$. On the other hand, this sum must be at least $503|V_1|$. It follows that $|V_1|\ge 1007$. A similar argument shows that $|V_2|\ge 1007$. Hence $V_1$ and $V_2$ cannot be disjoint.