There are $99$ space stations. Each pair of space stations is connected by a tunnel. There are $99$ two-way main tunnels, and all the other tunnels are strictly one-way tunnels. A group of $4$ space stations is called connected if one can reach each station in the group from every other station in the group without using any tunnels other than the $6$ tunnels which connect them. Determine the maximum number of connected groups.
Problem
Source: Chinese MO 1999
Tags: combinatorics proposed, combinatorics
25.03.2012 07:27
Lemma: A group is unconnected iff one of its stations has three intragroup tunnels leading away or three intragroup tunnels leading to it. Proof: Assume such a group $A,B,C,D$ is unconnected and specifically that $A$ cannot be reached from $B$; ergo $A$ leads to $B$. WLOG $D$ leads to $A$. Thus, $D$ leads to $B$ and then $B$ must lead to $C$. But $C$ must lead to at least one of $A$ or $D$; contradiction. The converse is trivial. Remark that each group can have at most one of each type of station. Each station $S$ borders 96 other stations not connected to it by a main tunnel. If there are $x$ tunnels leading into it and $y$ tunnels away (consequently), then there are $\binom{x}{3}+\binom{y}{3},x+y$ groups of four that contain $S$ as being one of the two types mentioned in the lemma. $\binom{x}{3}+\binom{y}{3}\ge \binom{48}{3}+\binom{48}{3}$ under these constraints is quickly apparent by the equality condition on RMS-AM; thus summing over all stations, there are at least $198\binom{48}{3}$ such types in groups total, and as each group can contain one type of each, we establish a minimum of $99\binom{48}{3}$ unconnected groups $\Rightarrow \binom{99}{4}-99\binom{48}{3}$. We can achieve this through a tournament in which each vertex defeats half the others (e.g. every other one besides the adjacents which have two-way tunnels). EDIT: I just realized it's not necessarily the case that the 99 two-way-tunnels connect adjacent stations so that each has two. But this is an easy fix, just simply sum over $\binom{x}{3}+\binom{y}{3}$ for all stations first and then note that $\sum x + y=99\cdot 98 - 2 \cdot 99$ and apply power mean equality from there.