# Using expected value to prove there exists a group of $7$ teams $A$ beats a group of $B$ in round-robin tournament

Here is an olympiad problem Iran TST 2008:

Suppose $799$ teams participate in a round-robin tournament. Prove that one can find two disjoint groups $A$ and $B$ of seven teams each such that all teams in $A$ defeated all teams in $B$.

Here is my solution using expected value. My idea is to find the expected value of number of pair of group $(A,B)$ so that either $A$ beat $B$ or $B$ beat $A$.

We randomly decide the result between any two teams. Hence, consider two groups of $7$ teams $A$ and $B$, the probability that either $A$ beats $B$ or $B$ beats $A$ is $\dfrac{1}{2^{7^2-1}}$. We call such pair $(A,B)$ good pair.

Consider all pair of disjoint groups $(A,B)$ in the tournament. Let $$X_i= \begin{cases} 1 \text{ if the ith pair (A,B) is good pair.} \\ 0 \text{ otherwise.} \end{cases}$$

Thus, the expected number of pairs of groups $(A,B)$ satisfying the above condition is $\displaystyle \mathbb{E}[X]= \sum_i \mathbb{E}[X_i]$. There are $\displaystyle \binom{799}{14}\binom{14}{7}$ disjoint groups $(A,B)$ so $$\mathbb{E}[X]= \binom{799}{14}\binom{14}{7} \cdot \frac{1}{2^{7^2-1}}.$$ It turns out that this expected value is huge, which make me doubt about the correction of my solution. I only need $\mathbb{E}[X]$ to be greater than $1$.

My question is: Is this solution correct? Are there other way to use expected value on this problem?

I'm afraid your solution is not correct - by deciding the outcome of each match randomly, you are studying a model of a random tournament. However, the question asks you to find these two groups of $7$ teams for any tournament with $799$ teams. Hence we must consider the outcomes of the match as fixed.

To use the probabilistic method, we can instead pick a random group $B$ of $7$ teams, and consider the expected number of teams that beats every team in $B$. So let $B$ be a set of $7$ teams uniformly at random. There are $\binom{799}{7}$ possible choices, each being equally probably. Let $X$ be the random variable counting the number of teams that beats every team in $B$.

Suppose (for notational convenience) the teams are labelled from $1$ up to $799$. Then we can write $X = \sum_{i=1}^{799} X_i$, where $X_i$ is $1$ if Team $i$ beats every team in $B$, and $0$ otherwise. By linearity of expectation, $$\mathbb{E}[X] = \mathbb{E} \left[ \sum_{i=1}^{799} X_i \right] = \sum_{i=1}^{799} \mathbb{E}[X_i].$$

Since $X_i$ only takes values in $\{0,1\}$, we have $$\mathbb{E}[X_i] = \mathbb{P}(X_i = 1) = \mathbb{P}(\textrm{Team } i \textrm{ beats every team in } B).$$

How do we compute this possibility? Let us introduce more notation: let $b_i$ be the number of teams that Team $i$ beats. Then $X_i = 1$ if and only if the set $B$ was chosen from the $b_i$ teams that Team $i$ beats. There are $\binom{b_i}{7}$ ways this can happen, and so $\mathbb{P}(X_i = 1) = \binom{b_i}{7} / \binom{799}{7}$. This gives $$\mathbb{E}[X] = \left( \sum_{i=1}^{799} \binom{b_i}{7} \right) / \binom{799}{7}.$$

This looks like a horrible sum, especially since we do not know the values $b_i$. However, convexity will come to our rescue. It turns out that the function $\binom{x}{7}$ is a convex function*, and so we can apply Jensen's inequality, which says that the lowest value the sum can take is when every $b_i$ is replaced with the average value $\overline{b} = \sum_{i=1}^{799} b_i / 799$.

Note that $\sum_{i=1}^{799} b_i$ counts every match exactly once (I assume there are no draws, so that every match has exactly one winner), and so $\sum_{i=1}^{799} b_i = \binom{799}{2}$, giving $\overline{b} = \frac{798}{2} = 399$. Thus $$\mathbb{E}[X] = \sum_{i=1}^{799} \binom{b_i}{7} / \binom{799}{7} \ge \sum_{i=1}^{799} \binom{\overline{b}}{7} / \binom{799}{7} = 799 \cdot \binom{399}{7} / \binom{799}{7} = 6.02549...$$

Since this expectation is strictly larger than $6$, there must be some choice of $B$ for which it is at least $7$. This gives a set $B$ of $7$ teams and a set $A$ of (at least) $7$ teams such that every team in $A$ beats every team in $B$. In particular, this implies $A$ and $B$ are disjoint, and we are done.

Note that the use of probability is not really required - this can easily be restated as a double-counting argument. We count the number of pairs $(i,B)$, where $B$ is a set of $7$ teams that Team $i$ beats. The number of pairs is $\sum_{i=1}^{799} \binom{b_i}{7}$, which we can lower bound with Jensen's inequality. On the other hand, averaging over the $\binom{799}{7}$ choices for $B$, we find there must be one with at least $7$ possible teams $i$, and we are done.

*One small detail regarding the application of Jensen's inequality. The extension of the binomial coefficient to the real numbers is given by $$\binom{x}{7} = x(x-1)(x-2)...(x-6)/7!.$$ This is convex for $x \ge 6$, but we may well have some degrees $b_i$ below $6$, in which case we could not apply Jensen's straight off the bat. However, we can instead apply it to the modified function $$\binom{x}{7}^* = \begin{cases} \binom{x}{7} & x \ge 6 \\ 0 & x \le 6 \end{cases}.$$ One can check that this is convex over $\mathbb{R}$, and it agrees with the usual binomial coefficient over all integers, and hence we can apply Jensen's without fear.

• Thank you very much for your help Shagnik. – Tengu Sep 26 '16 at 1:31
• You're welcome, happy to help! – Shagnik Sep 26 '16 at 5:51