2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.