there is a team that won more than 13games......(trivial...) select this team(call this team A) and other 13teams those lost to A. then we pick 14teams and divide them into two groups(1 to 13) as condition.. something strange

I think a group of 14 teams should be partitioned into 2 groups with 7 teams. (Case "2 and 12" is also easy.)

Official Solution: Throughout this solution, $ a^+$ denotes $ \max\{a,0\}$. Consider the tournament as a directed graph, where an edge from $ v$ to $ u$ shows that $ v$ has won its game against $ u$. Let's count the number of directed $ 7$-paw's. (An $ n$-paw is a subgraph consisting of $ n$ edges coming out from a vertex) If the out degree of vertices are denoted by $ d_i$ then this number is obviously equal to $ \sum_i{d_i\choose 7}$. Assuming that the claim of the problem is not satisfied, for each $ 7$ vertices there are at most $ 6$ vertices having edges coming out to each of those $ 7$. Hence the number of $ 7$-paw's is at most $ 6{n\choose 7}$ where $ n$ is $ 799$, the number of vertices. The remaining parts of the proof try to show that $ \sum_i{d_i\choose 7}>6{n\choose 7}$. Let $ a_i=(d_i-6)^+$. Then $ {d_i\choose 7}=\frac{d_i(d_i-1)\dots(d_i-6)}{7!}=\frac{a_i(a_i+1)\dots(a_i+6)}{7!}$. This is because if $ d_i>6$, then $ a_i=d_i-6$ and this identity obviously holds. And if $ d_i\leq 6$ then both sides are $ 0$ and the identity still holds. Now let $ f(x)=\frac{x(x+1)\dots(x+6)}{7!}=\sum_ic_ix^i$. Of course $ c_i$'s are all non-negative. \[ \sum_i{d_i\choose 7}=\sum_if(a_i)=\sum_i\sum_jc_ja_i^j=\sum_jc_j\sum_ia_i^j\]Note that $ c_0=0$. For $ j\geq1$, we have the following inequality between $ j^{th}$ exponents mean and arithmetic mean.\[ \left(\frac{\sum_ia_i^j}{n}\right)^{\frac 1j}\geq\frac{\sum_ia_i}n\] But since our graph is a tournament $ \sum_id_i={n\choose 2}$. Hence $ \sum_ia_i\geq{n\choose 2}-6n$. This shows that $ \frac{\sum_ia_i}n=\frac{n-1}2-6=\frac{n-13}2$. Name this constant as $ A$. Substituting in our inequality gives \[ \sum_ia_i^j\geq nA^j\]Now substituting in our previous identities, we get \[ \sum_i{d_i\choose 7}\geq\sum_jc_jnA^j=n\sum_jc_jA^j=nf(A)\]But $ f$ is defined so that $ f(x)={x+6\choose 7}$. So $ nf(A)=n{\frac{n-1}2\choose 7}$. A straightforward calculation reveals that this number is $ 242071561222413021$ while $ 6{n\choose 7}$ is $ 241047478096826154$, a slightly smaller number. This completes the proof.

A count-twice works in the same way as well : Let $X_i$ be the teams. Construct the set $\mathcal{T} = \left \{ \left ( X_1,\cdots , X_7 \right ),(X_{looser}) \right \}$, where $X_{looser}$ is defeated by all of $X_1,X_2, \cdots, X_7$. On the contrary assume that number of teams defeated by all of any set of $7$ other teams is less than equal to $6$. So $|\mathcal{T}|\le 6\cdot \binom{799}{7}$. We count it in another way :Let $X_i$ be defeated by $n_i$ number of teams, so $|\mathcal{T}| = \sum_{i \in \text{teams}}^{{}}\binom{n_i}{7}$. Also note that $\sum_{i \in \text{teams}}^{{}}n_i = \binom{799}{2}$. So we have $\sum_{i \in \text{teams}}^{{}}\binom{n_i}{7} \le 6\cdot \binom{799}{7} $. Which can be proved to be false,(as above) and hence the problem statement is true.

Consider some set of guys $|A|=7$ and let $X$ be the set of guys beaten by all the guys from $A.$ Let $X_i :=1$ if i-th player is in $X,$ otherwise $0.$ We have $$\mathbb E[X]=\sum_{i=1}^{799-7}\mathbb E[X_i]=\sum_{i=1}^{799-7}(\frac{1}{2})^7=\frac{792}{128}=6.1875 >6$$Thus, there is some configuration such that $X \ge 7$ and just take any $B \subset X.$

Hi everyone, I did exactly the same thing as SidVicious, but it seems so simple that I doubt it's working...Why the official solution is so hard if the one proposed by SidVicious, which is not hard to find, is true ? Seems strange :s Moreover, the solution proposed above by SidVicious seems imply that for any set of 7 people, we can find another set of 7 people checking the conditions. Isn't it weird ?

I don't think $\sum_{i=1}^{799-7}{\mathbb E[X_i]}=\sum_{i=1}^{799-7}{(1/2)^7}$ is true. Even if you choose $|A|$ with equal probability from each of $799$ teams, the probability of a team being beaten by team $A_j\in A$ is fixed (and usually not equal to $1/2$).

This kind of flaw doesn't encourage me to use expectation in combo. It's so magic that I don't understand what I do. Even here, where there's obviously a problem, I don't really understand where the prooblem is... EDIT : Ok I did understand my mistake, and it was a big one. Actually, the tournament can't be generate with randomize procedure. Otherwise, we'll show that "for some" tournaments, there will be a tournament which fullfill conditions, but it's not at all the question. So we have to consider a given tournament, and then we can use randomization to choose a team or something else. It's exactly what Dark Lord said I know ^^

Here is a generalization proved using the probabilistic method: Generalisation wrote: In a tournament with $n$ teams, let $k,l$ be integers satisfying $$n{{(n-1)/2}\choose{k}}>(l-1){{n}\choose{k}}$$Then there exist two sets of teams $A, B$ with $k, l$ teams respectively such that each team in $A$ beat each team in $B$. Note: If we say a set of teams $X$ beat a different team $U$, then that means all members of $X$ beat $U$. Randomly choose a set $A$ with $k$ teams. Let $X$ denote the number of teams $A$ has defeated, and let $D_i$ denote the event that $A$ defeated the team $i$. Further, for any team $i$, let $z_i$ denote the number of teams that $i$ lost to. Hence $$\mathbf{E}[X]=\sum_i \mathbf{P}[D_i]=\sum_i {{z_i}\choose{k}} \cdot {{n}\choose{k}}^{-1} \geq n{{(n-1)/2}\choose{k}} \cdot {{n}\choose{k}}^{-1} > l-1$$Hence, there exists a set $B$ of $l$ teams such that $A$ beat $B$, as desired. $\blacksquare$ For the given problem, set $n=799$ and $k=l=7$.

To #6 - the expected value is wrong ! To arrive at the inequality is easy $\sum_i{d_i\choose 7}>6{n\choose 7}$ The rest is algebra (this is an algebra prob. rather than combi ! Even one can NOT use Jensen to derive that inequality !)

For a team $x$, let $\lambda(x)$ denote the set of teams $x$ beat, and let $\omega(x)$ be the set of teams $x$ lost to. The problem is equivalent to showing that there exist $7$ teams $x_1,\ldots,x_7$ with \[|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|\ge 7.\]As usual, we'll compute \[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|).\]For each fixed team $y$, the probability it is in this intersection is just \[\frac{\binom{|\omega(y)|}{7}}{\binom{799}{7}},\]so by linearity of expectation, \[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|)=\sum_{y\in\tau}\frac{\binom{|\omega(y)|}{7}}{\binom{799}{7}}\]where $\tau$ is the set of teams. Note that the average value of $\omega(y)$ is $\frac{\binom{799}{2}}{799}=782/2$ since there are a total of $\binom{799}{2}$ losses. Thus, by Jensen, \[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|)\ge\frac{799}{\binom{799}{7}}\binom{\frac{798}{2}}{7}.\]It is a computation to verify that \[\frac{799}{\binom{799}{7}}\binom{\frac{798}{2}}{7}>6,\]so we're done, since there must be some $x_1,\ldots,x_7$ with \[|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|>6.\] Remark In our use of Jensen's inequality, we assumed the function $f(x):=\binom{x}{7}$ is convex, which strictly speaking holds only for $x\ge 7$. The fix for our purposes is to define $\tilde{f}(x)=\binom{x}{7}$ for $x\ge 7$ and $\tilde{f}(x)=x-6$ for $6\le x<7$, and $\tilde{f}(x)=0$ for $0\le x<6$. This matches $\binom{\bullet}{7}$ wherever we need it to, and is now correctly convex.

Let team $i$ win $c_i$ games; note $c_1+...+c_n={799\choose 2}$. Randomly choose a set B of 7 teams. For each team T, the probability that T beat all teams in B is $\frac{{c_i\choose 7}}{{799\choose 7}}$ so by linearity of expectation, the expected number of teams that B completely lost to is $\frac{{c_1\choose 7}+...+{c_{799}\choose 7}}{{799\choose 7}}\ge \frac{799{399\choose 7}}{{799\choose 7}}>6$ (by Jensens) which finishes the problem.

Let $a_i$ denote the number of games that each team won to. Then, $\binom{a_i}{7}$ is the number of sets of $7$ teams that were all beaten by team $i$. If we add this up for all of the teams, then we obtain by Jensen's \[ \sum \binom{a_i}{7} \ge 799 \binom{399}{6} > 6 \cdot \binom{799}{7} \]Since there are $\binom{799}{7}$ sets of $7$ teams in total, there exists groups $A$ and $B$ of seven teams each such that each team in $A$ beat each team in $B$.

We randomly select a group of $7$. Now, the idea is to sum up all loss-counts for the $792$ other people. If $l_i$ is the number of losses of person $i$, then the expected number of losses to the 7-group is $$\frac{1}{\binom{798}{7}} \cdot \sum_{i = 1}^{792} \binom{l_i}{7} \geq 792 \cdot \frac{\binom{399}{7}}{\binom{798}{7}},$$which we can verify is between $6$ and $7$, hence done.

Let $c_i$ be the number of teams that team $i$ beat. Then, firstly note that \[\sum_{i=1}^{799} c_i = \text{ number of matches } = \binom{799}{2}\]Now, by Jensen's, since $\binom{x}{7}$ is convex we have that \[\text{the number of sets $(A,B_1,B_2,\ldots B_7)$}= \sum_{i=1}^{799} \binom{c_i}{7} \geq 799 \cdot \binom{\frac{\sum c_i}{799}}{7}=799 \cdot \binom{399}{7}\]Summing over all $(B_1,B_2,\ldots B_7)$, the average number of people who have beaten everyone in this group is \[\frac{ \sum_{i=1}^{799} \binom{c_i}{7}}{\binom{799}{7}}\geq \frac{799\cdot \binom{399}{7}}{\binom{799}{7}}= \frac{(396\cdot395\cdot394\cdot393)}{2^{3}\cdot(797\cdot795\cdot793)} = \frac{(99\cdot79\cdot197\cdot131)}{(797\cdot53\cdot\left(13\cdot61\right))}>6 \]Thus, by pigeonhole there is some group $(B_1,B_2,\ldots B_7)$ such that there is a group of size 7:$(A_1,\ldots A_7,)$ such that all teams in A beat all teams in B.

We just have to double-count the number of pairs $T = \left \{ \left ( A_1,\cdots , A_7 \right ),(A) \right \}$, where $A$ has lost all matches with the $A_i$. If $A$ has lost $n_i$ matches, then $\sum^{{}}\binom{n_i}{7} \le 6\cdot \binom{799}{7} $, where the bounding contradiction is achieved with Jensen.

We count the number of pairs $(P, S)$, where $P$ is a player and $S$ is a set of $7$ players that $P$ beat. If we let $w_i$ be the number of wins each person had, the sum is $\sum \dbinom{w_i}{7}$, and by Jensen's, the minimum is $799 \cdot \dbinom{399}{7}$. There are exactly $\dbinom{799}7$ values of $S$. By Pigeonhole, one of them appears at least $\frac{799 \cdot \dbinom{399}7}{\dbinom{799}7} > 6$ times, which finishes.

Let $\ell_i$ denote the number of losses that the $i$th team. Notice that there is ${\ell_i \choose 7}$ groups of $7$ that have all beaten team $i$. Now summing this over all $i$, we receive that $$\sum_{i} {\ell_i \choose 7} > 799 \cdot {399 \choose 7}$$which is true by Jensen's. Now this is equal to the total number of times a group of $7$ have all beaten a singular person. Now we want to find the expected value of people that a random group of $7$ have commonly beaten, call this $X$. Note that $$\mathbb{E}[X] > \frac{799 \cdot {399 \choose 7}}{{799 \choose 7}} > 6$$so we are done.

Another standard global problem: The heuristic is usually to compute expected value with counting and Jensen's. Take a directed connected graph G, where vertices represent teams. We sample $A$ randomly from the $799$ teams and compute the number of teams defeated by everyone in $A$; a team v is expected to lose to every team in A with probability $$\frac{{\binom{\text{indeg} v}{7}}}{{\binom{799}{7}}}\implies A\text{(\# of wins)}= \frac{1}{\binom{799}{7}} \sum_v \binom{\text{indeg} v}{7} \overset{\text{Jensen}}{\ge} \frac{1}{\binom{799}{7}}799 \binom{399}{7}>6,$$so there's a group of seven teams that each team of A beat, as desired. $\blacksquare$

Randomly choose a set of 7 "loser" teams. Then, we call a team good if it defeated all 7 loser teams. The probability of a team with $w$ wins being good is $$\frac{{w\choose 7}}{{799\choose 7}}$$since all 7 randomly chosen teams must be in would of the $w$ teams that it beat. By Jensen's Inequality, since ${w\choose 7}$ is convex, and the sum of all $w_i$ is constant (equal to 799 choose 2), this is minimized when all $w_i$ are equal (equal to 399). Thus, the expected number of good teams is at least $$799\cdot \frac{{399\choose 7}}{{799\choose 7}}\approx 6.03,$$which is greater than 6, so some way must achieve at least 7 good teams.

Let $W$ be the number of wins a team has. Then the probability that the team beats a given group of $7$ teams is $\frac{\binom{W}{7}}{\binom{799}{7}}$. Then the expected value of teams that beat the given $7$ teams is $\cdot \frac{\binom{W_i}{7}}{\binom{799}{7}}$ for all teams $i$. Then by Jensen's since $\binom{W}{7}$ is convex, we have $\frac{\binom{W_i}{7}}{\binom{799}{7}} \geq 799 \cdot \frac{\binom{399}{7}}{\binom{799}{7}} > 6$, so we are done. (I'm not really sure how people got that the final expression is greater than $6$ without a calculator lol)