Is it correct?? Consider the team $T_i$ with the minimum no. of losses.Let this minimal no be atleast 5.Take any 5 teams which has won with $T_i$ along with $T_i$ and form a subset of 55 teams taking 49 other teams.In this subset there exists a team other than $T_i$ with losses $\le 4$.It follows that that team will have a corresponding team not in the subset with which it has lost.Include the team originally outside the subset in the subset by eliminating another team.Continuing this way we can eventually find a subset of 55 teams with all losing $\ge 5$ in the subset,a,c ontradiction

Seems that my solution is not correct.Any solutions please??

Bump... Anyone ?

Claim: For $k\ge 55,$ if in any set of $k$ teams, there is one which has lost to no more than $4$ of the remaining $k-1$ teams, then in any set of $k+1$ teams, there is one which has lost to no more than $4$ of the remaining $k$ teams as well. Proof. Suppose contrary, there exists a set $M=\{C_1,C_2,\dots,C_{k+1}\}$ such that each $C_i$ has lost to at least $5$ teams among $M-\{C_i\}.$ By our induction hypothesis there exist $C_j$ such that $C_j$ has lost to no more than $4$ in $M-\{C_i\},$ i.e. $C_j$ has lost to exactly $5$ teams and $C_i$ is one of them. Hence we consider a mapping \[f:M\mapsto M\mid f(C_i)\stackrel{\text{def}}{=}C_j.\]Clearly $s=\mid f(M)\mid \ge \lceil{\tfrac{k+1}{5}}\rceil\ge 12.$ Consider the tournament among that $s$ teams, by PHP one of them has lost to at least $\tfrac{\tbinom{s}{2}}{s}=\tfrac{s-1}{2}>5,$ which contradicts the result above(they has lost to exactly $5$ teams). $\square$

Complex2Liu wrote: Claim: For $k\ge 55,$ if in any set of $k$ teams, there is one which has lost to no more than $4$ of the remaining $k-1$ teams, then in any set of $k+1$ teams, there is one which has lost to no more than $4$ of the remaining $k$ teams as well. Proof. Suppose contrary, there exists a set $M=\{C_1,C_2,\dots,C_{k+1}\}$ such that each $C_i$ has lost to at least $5$ teams among $M-\{C_i\}.$ By our induction hypothesis there exist $C_j$ such that $C_j$ has lost to no more than $4$ in $M-\{C_i\},$ i.e. $C_j$ has lost to exactly $5$ teams and $C_i$ is one of them. Hence we consider a mapping \[f:M\mapsto M\mid f(C_i)\stackrel{\text{def}}{=}C_j.\]Clearly $s=\mid f(M)\mid \ge \lceil{\tfrac{k+1}{5}}\rceil\ge 12.$ Consider the tournament among that $s$ teams, by PHP one of them has lost to at least $\tfrac{\tbinom{s}{2}}{s}=\tfrac{s-1}{2}>5,$ which contradicts the result above(they has lost to exactly $5$ teams). $\square$ Nice solution. I would just point out that for a given $C_i$, the $C_j$ might not be unique, so the mapping is not well-defined. This is hardly a problem though because you could just consider the $C_j$ with $j$ minimal.

JackXD wrote: Seems that my solution is not correct.Any solutions please?? JackXD wrote: Is it correct?? Consider the team $T_i$ with the minimum no. of losses.Let this minimal no be atleast 5.Take any 5 teams which has won with $T_i$ along with $T_i$ and form a subset of 55 teams taking 49 other teams.In this subset there exists a team other than $T_i$ with losses $\le 4$.It follows that that team will have a corresponding team not in the subset with which it has lost.Include the team originally outside the subset in the subset by eliminating another team.Continuing this way we can eventually find a subset of 55 teams with all losing $\ge 5$ in the subset,a,c ontradiction This doesn't work because you include the team originally outside the subset by eliminating another team, and then you continue like that; what if at some step you have remove this team that you just added...

We prove the result is true if $110$ is replaced by any $N \ge 55$. To see this, we proceed by induction on $N$, with the base case given. Assume for contradiction that we have $N+1$ people such that each team lost at least five times, but within every $N$ some team lost at most four times. In that case, a champion is a team which lost exactly five times. Lemma: There are at most $11$ champions. Proof: Otherwise, note that when $12$ champions play each other, they each lose on average $5.5$ games to each other, contradiction. On the other hand, note that for any person $p$, some champion lost to $p$ (by inductive hypothesis). Thus there are at least $\tfrac15(N+1)$ champions. For $N \ge 55$ this is a contradiction.

Complex2Liu wrote: Clearly $s=\mid f(M)\mid \ge \lceil{\tfrac{k+1}{5}}\rceil\ge 12.$ Can someone explain this part of the problem?

Russian Mathematical Olympiad 2015 11th grade Problem 3 wrote: $110$ teams participate in a volleyball tournament. Every team has played every other team exactly once (there are no ties in volleyball). Turns out that in any set of $55$ teams, there is one which has lost to no more than $4$ of the remaining $54$ teams. Prove that in the entire tournament, there is a team that has lost to no more than $4$ of the remaining $109$ teams.

Nice problem! We set up the following induction: for every set $S$ of teams, there exists a team in $S$ that lost to no more than $4$ of the remaining teams in $S$. We will induct on $|S|$ with the stipulation that $|S| \geq 55,$ and the base case has been given in the statement. For convenience set $n = |S|$. Suppose for the sake of contradiction that no team in $S$ has been beaten four or less times by the remaining teams in $S$. By the inductive hypothesis, every $n-1$ element subset in $S$ contains a team that has only been beaten four times by the remaining teams in the subset; call such teams strong. Now these teams have been beaten exactly $5$ times total, so a team $t$ can be strong for exactly $5$ subsets (the $5$ subsets excluding the five teams $t$ lost to). Suppose there are $s$ strong teams; since we need a strong team for each of the $n$ subsets, we derive a lower bound of $s \geq n/5 \geq 12$ strong teams. But now note that each strong team can lose to at most $5$ other strong teams. On average, each strong team loses to $\tfrac{s-1}{2}$ other strong teams; for $s \geq 12$ this implies that some strong team loses to more than $5$ teams, a contradiction.

The idea is to show that for all $n \geq 55$ there is a team among these $n$, who has at most 4 losses. We induct; suppose that the statement is true for $n$ but not true for $n+1$, i.e. each team among these $n+1$ teams $T_1, T_2, \cdots, T_{n+1}$ has at least 5 losses, but removing any team $T_i$ yields a team $T_j$ with at most 4 losses (i.e. exactly 4 and one additional from $T_i$). Assign $T_j$ to $T_i$, then there are at least $n+1$ assignments, and each team is assigned at most 5 times, so there are at least $\lceil{\frac{n+1}{5}}\rceil \leq 12$ teams assigned at least ones. These teams have 5 losses each, but the total number of losses among them is at least $66$, so some team has lost at least $6$ times, contradiction.

Assume the opposite, i.e. any team lost at least $5$ matches. Claim. There at most $11$ teams, which lost exactly $5$ matches. Proof. Pick any $12$ teams; they played $66$ games between themselves, so by Pigeonhole Principle some picked team lost at least $6$ games. Hence the conclusion $\Box$ Now for any choice of $55-$element set of teams pick all teams from this set, which lost to no more than $4$ of the other $54$ teams. Thus we picked at least $\binom{110}{55}$ teams (including the repeat). On the other side, at most $11$ teams lost $5$ games, and so were picked at most for $\binom{109}{55}-\binom{104}{49}$ times; others lost at least $6$ games, and so were picked at most for $$\binom{109}{54}-\left( 1+\binom{6}{5}\right) \cdot \binom{103}{48}$$times. But by straightforward check the inequality $$110\binom{109}{54}-11\binom{104}{49}-7\cdot 99\binom{103}{48}\geq \binom{110}{55}$$fails, hence the contradiction.

Take the obvious graph interpretation. Assume for the sake of contradiction that the conclusion is false. The key is to construct a subset of vertices $H \in G$ such that $|H|$ is minimal, and each vertex in $H$ has indegree at least $5$ in $H$. Notice that $|H| > 55$. Claim. There are at least $12$ vertices in $H$ that have indegree exactly $5$. Proof. Let $S$ be the set of all vertices with indegree exactly $5$. Observe that if there exists a vertex $v$ for which none of the out-pointing arrows point to vertices with indegree $5$, this vertex can be removed, contradicting minimality. Thus, the total number of vertices is upper bounded by $5$ times the number of such vertices. As a result, $|S| \geq \frac 15 |H| > 12$. $\blacksquare$ Now consider the complete graph $S$. The vertex in $S$ with the maximal indegree must have indegree at least $\lceil 11/2 \rceil = 6$, which contradicts the definition of $S$.

Say that a team $T$ is a dominator of a group of teams $G$ if $T$ had at most 4 losses against other members of $G$. Claim 1: In any tournament, at most $11$ teams have at most $5$ losses. Suppose FTSOC there are 12 such teams. Then, they played 66 games among each other, so some team has at least 6 losses, contradiction. Now, we go to the main part of the problem: Claim: If $n\geq 55$ is a positive integer such that all groups of $n$ teams have a dominator, then all groups of $n+1$ teams also has a dominator. Suppose FTSOC that in a group of teams $T_1\dots T_{n+1}$ each team has at least 5 losses within its group. Then, consider $n$ team subsets of these $n+1$ teams. We know that each $n$ team subset has a dominator. This means that a dominator of any set of $n$ teams must have lost to the team that is not chosen since we are assuming that it is not a dominator of the entire set. Furthermore, if a team $T$ is a dominator of an $n$ element subset, it can have at most 5 losses within the $n+1$ team group. Hence, by Claim 1, at most 11 teams are eligible to be a dominator. Since $n+1\geq 56$, some team must be a dominator of at least 6 groups of size $n$, and hence has at least 6 losses as the dominator must lose to the excluded team, contradiction as if it has 6 losses it cannot be a dominator of an $n$ team group at all. Thus, by induction, all groups of size $110$ have a dominator, so we are done. \begin{remark} If 4 is replaced with $n$, this solution idea still works if 55 is replaced with $(n+1)(2n+3)$ and 110 is replaced with $2(n+1)(2n+3).$ \end{remark}

Kind of doubting my solution as I found a way stricter bound than the given. Does anyone mind checking it? Claim: Consider a tournament graph $G$ with $N$ teams, where $N \geq 25$, such that each team loses at least 5 times. Then, there exists a sub-tournament with $N - 1$ teams such that each team loses at least $5$ times (among those $N - 1$ teams). Proof: Call the teams that lose exactly $5$ times "elite," and let $K$ be the number of such teams. We show that there exists a non-elite team that loses against all elite teams. Then, the sub-tournament with all teams except this non-elite team satisfies the condition, since each elite team would still have $5$ losses and each non-elite team would still have $\geq 6 - 1 = 5$ losses. Note that $K \leq 11$. Otherwise, among the $\geq 12$ elite teams, there would be at least one team with six losses to other elite teams, a contradiction. Now, there are exactly $5K - K(K - 1) / 2$ games where a non-elite team wins against an elite team. But note that there are exactly $(N - K)$ non-elite teams. For $N \geq 25$, note that $N \geq 25 > K(13 - K) / 2$, so $(N - K) > 5K - K(K - 1) / 2$. This implies that there exists a non-elite team that loses against all elite teams. Therefore, if there exist a tournament $110$ teams where each team loses to at least $5$ other teams, by induction, there must exist a tournament of $109, 108, \dots, 55$ teams where each team loses to at least $5$ other teams, contradicting the initial assumption that in every group of $55$ teams, there exists a team which has lost to at most four other of the other $54$ teams.

We proceed by induction on $N \ge 55$. The base case is trivial. Assume that the result holds for some $N$. We will prove that it is true for $N+1$ too. FOTSOC, assume that it is false. Thus, every team lost at-least $5$ matches but in sub-groups of $N$, a team$T$ lost at-most $4$ matches. Thus team $T$ lost exactly $5$ matches amongst other $N$ teams. Let $S$ denote the set of teams. Define a function $f: S \to S$: $f(T_i) = T_j$ if we run inductive hypothesis on $S-\{T_i\}$, then $T_j$ denote the team which lost to $T_i$ and lost to exactly $5$ other teams in $S$. Let the image of function $f$ be $G$. For every team $T \in G$, it lost to exactly $5$ other teams in $S$. Thus: $$|G| \ge \lceil \tfrac{N}{5} \rceil \ge 12.$$ Now, consider the set of teams $T_w$ which lost to exactly $5$ other teams. Note that $|T_w| \le 11$. If not, then consider $|T_w|=12$. Then, the expected value of a team losing to other team amongst $T_w$ is $\frac{11}{2} = 5.5$ which implies some team lost to atleast $6$ other teams. Contradiction. Thus, $|T_w| \le 11$. But notice that: $G \in T_w$ but $|G| \ge 12 > 11 \ge |T_w|$ which leads to contradiction.

We prove the stronger claim that the desired condition holds for any $N \ge 55$ teams. To do this, we use induction on $N$, with the base case being given in the problem statement. Let the set of all of the teams be $T$. Assume that the inductive hypothesis holds for $N$ teams; that is, for any subset $S \subseteq T$ such that $|S| = N$, there exists a team in $S$ that has lost to at most $4$ other teams in $S$. Denote such teams as champions. FTSOC suppose that every team in $T$ loses at least $5$ times to other teams in $T$. Then, it is clear that the champions lose $4$ times in their respective $S$ and then lose to the team that is not in $S$. Hence, each team beats a champion, giving us \[5c \ge |T| = N+1 > 55,\] where $c$ is the number of champions. This yields $c>11$. However, among the set of champions, there is an average of $\tfrac{c-1}{2}$ losses per champion, which cannot exceed $5$. This gives us $c \le 11$, a contradiction. $\blacksquare$