$30$ volleyball teams have participated in a league. Any two teams have played a match with each other exactly once. At the end of the league, a match is called unusual if at the end of the league, the winner of the match have a smaller amount of wins than the loser of the match. A team is called astonishing if all its matches are unusual matches. Find the maximum number of astonishing teams.
Problem
Source: 2017 Iran MO 3rd round, second combinatorics P3
Tags: Iran, combinatorics
12.09.2017 19:46
Let those $30$ teams be $T_1,T_2,...,T_{30}$. For each $i\in \{ 1,2,...,30\}$, suppose that $T_i$ won $w_i$ times. For each astonishing team $T_{\ell}$, there's $29-w_{\ell}$ teams which defeated $T_{\ell}$, so those $29-w_{\ell}$ values of $w_i$s are smaller than $w_{\ell}$. For any two distinct astonishing teams (if exist) $T_{\ell_1},T_{\ell_2}$, if $w_{\ell_1}>w_{\ell_2}$, there must be more $w_i$s whose value is smaller than $w_{\ell_1}$ than those whose smaller than $w_{\ell_2}$. This gives $29-w_{\ell_1}>29-w_{\ell_2}\implies w_{\ell_2}>w_{\ell_1}$, contradiction. The same argument also work if $w_{\ell_2}>w_{\ell_1}$. So, we conclude that $w_{\ell_1}=w_{\ell_2}$. But there's again a contradiction when we consider the match between $T_{\ell_1}$ and $T_{\ell_2}$. Hence, there exists at most one astonishing team. The rest is to give an example. Let $T_1$ be the team we want to make it astonishing team and let $w_1=15$. Let $T_1$ defeated $T_2,T_3,...,T_{16}$ and was defeated by $T_{17},T_{18},...,T_{30}$. This required $w_2,w_3,...,w_{16}>w_1=15>w_{17},w_{18},...,w_{30}$. For each $i\in \{ 2,3,...,16\}$ and $j\in \{ 17,18,...,30\}$. Let $T_i$ defeated $T_j$. So, $T_j$ defeated at most $14$ teams (from $\{ T_1,T_{17},T_{18},...,T_{30}\}$ exclude itself), smaller than $w_1=15$. And $T_i$ defeated at least $14$ teams (from $\{ T_{17},T_{18},...,T_{30}\}$), we have to choose at least other two from $\{ T_2,T_3,...,T_{16}\}$. This is clearly possible, just let $T_i$ defeated $T_{i+1},T_{i+2}$ for all $i\in \{ 2,3,...,14\}$, $T_{15}$ defeated $T_{16},T_1$ and $T_{16}$ defeated $T_1,T_2$. For other unknown matches, the result can be anything. Hence, we've met our only requirement, done.
24.08.2020 11:33
suppose we have $t$ astonishing teams $( A_1 , … , A_t)$ and the total wins are $(a_1 \leq … \leq a_t)$ , in a play between $A_i , A_j$ which $i<j$ , $A_i$ should win so we should have $(a_1 < … <a_t)$ so $a_1\geq t-1$ $\rightarrow $ $\forall i \leq t ; a_i \geq t+i-2 $ so $A_t$ wins at least $2t-2$ other person , they should have at least $2t-1$ wins . other $32-3t$ person have at least $\binom{32-3t}{2} + (32-3t)t$ wins . so $t(32-3t) +\frac{(3t-3)t}{2} +(2t-1)(2t-2) + \binom{32-3t}{2} \leq \binom{30}{2} \longrightarrow t\leq 9$ and it's easy to check that $t=9$ works $\blacksquare$
12.09.2020 07:42
$\mathrm{ }$