$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that \[\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.\] Proposed by Sung Yun Kim, South Korea
Problem
Source: IMO Shortlist 2010, Combinatorics 5
Tags: combinatorics, IMO Shortlist, graph theory, Tournament graphs, vertex degree, Hi
19.07.2011 03:14
19.07.2011 03:58
Lovely. If I'm not mistaken, your solution gives in general that $\sum(w_i - \ell_i)^3 = 24(b - d)$, right? The result $\sum w_i^2 = \sum \ell_i^2$ is actually an old Putnam problem: https://www.artofproblemsolving.com/Forum/viewtopic.php?f=150&t=10992 This reminded me immediately of it. One major difference is that the Putnam result is valid for any regular directed graph (not just tournaments), while this result is not as stated: for example, consider $K_{3, 3}$ directed so that one side has indegrees 3, 3 and 0.
19.07.2011 05:29
JBL wrote: Lovely. If I'm not mistaken, your solution gives in general that $\sum(w_i - \ell_i)^3 = 24(b - d)$, right? The result $\sum w_i^2 = \sum \ell_i^2$ is actually an old Putnam problem: https://www.artofproblemsolving.com/Forum/viewtopic.php?f=150&t=10992 This reminded me immediately of it. One major difference is that the Putnam result is valid for any regular directed graph (not just tournaments), while this result is not as stated: for example, consider $K_{3, 3}$ directed so that one side has indegrees 3, 3 and 0. Yes, you do always obtain $\sum(w_i - \ell_i)^3 = 24(b - d).$ Funny thing, I actually found $\sum w_i^2 = \sum \ell_i^2$ in a completely different setting, and then realized the same technique could be applied to this problem.
28.07.2011 15:03
We'll prove by induction on the number of people. The base case $n=4$ is easy enough. Let $v_{ij}=1$ if the $i$th player beat the $j$th player, and $-1$ otherwise. It's clear that $d_i=w_i-\ell_i=\sum_{j \ne i} v_{ij}$, and $\sum_{i=1}^{n} d_i = \sum_{i=1}^{n} w_i - \sum_{i=1}^{n} \ell_i =0$. Excluding the $\ell$th vertex, the inductive hypothesis implies $\sum_{i \ne \ell} (\sum_{j \ne i, \ell} v_{ij} )^3 = \sum_{i \ne \ell} (d_i - v_{i \ell})^3 \ge 0$. Summing over all vertices we have $ \sum_{\ell=1}^n \sum_{i \ne \ell} (d_i - v_{i \ell})^3 = \sum_{i=1}^n \sum_{\ell \ne i} (d_i - v_{i \ell})^3$ = $ \sum_{i=1}^n (d_i^3(n-1)-3d_i^2 \sum_{\ell \ne i} v_{i \ell} + 3d_i \sum_{\ell \ne i} v_{i \ell}^2 - \sum_{\ell \ne i} v_{i \ell}^3)$ $= \sum_{i=1}^n (d_i^3(n-1)-3d_i^3 + 3d_i (n-1) - d_i)$ $= (n-4)\sum_{i=1}^n d_i^3 \ge 0$ It follows $\sum_{i=1}^n d_i^3 \ge 0$ since $n>4$ which is equivalent to what we wanted to show. Thanks darij grinberg for pointing out my error
30.07.2011 01:34
@malcolm: I think you have a bug in this computation: $ \sum_{\ell=1}^n \sum_{i \ne \ell} (d_i - v_{i \ell})^3 = \sum_{i=1}^n \sum_{\ell \ne i} (d_i - v_{i \ell})^3$ = $ \sum_{i=1}^n (d_i^3(n-1)-d_i^2 \sum_{\ell \ne i} v_{i \ell} + d_i \sum_{\ell \ne i} v_{i \ell}^2 - \sum_{\ell \ne i} v_{i \ell}^3)$ $= \sum_{i=1}^n (d_i^3(n-1)-d_i^3 + d_i (n-1) - d_i)$ $= (n-2)\sum_{i=1}^n d_i^3 \ge 0$. (This is the computation you do directly after writing "Summing over all vertices we have".) $\left(a-b\right)^3$ is $a^3-3a^2b+3ab^2-b^3$, not $a^3-a^2b+ab^2-b^3$. Still it works (you get $\left(n-4\right)\sum_{i=1}^n d_i^3$, however). EDIT: The above-mentioned bug has been fixed now.
14.08.2011 09:51
This problem was proposed by me. I heard that this was one of the two candidates for the 2010 IMO #5... so close. My original solution is almost the same as abacadaea's one.
14.10.2014 04:57
I have discovered a solution which I consider wholly remarkable! First note that the inequality trivially holds for $n=2,3$ as well. Take player $X$ with the most losses; if there are multiple take any. Now we prove a lemma: Lemma: There exists a player $Y$ who defeated everyone who defeated $X$, as well as $X$. Proof: Out of the group of players who defeated $X$, pick the one with the most wins within the group $Y$. (If there are multiple take any; there aren't multiple.) Now take some $Z$ who lost to $Y$ and some $Q$ who lost to $Z$. By the condition on the group $(X,Y,Z,Q)$, we must have $Y$ defeat $Q$. By reaching over all those who $Y$ defeated, we find that either $Y$ defeated everyone or that there exists a subset of players who defeated not only $Y$ but all those he beat. Then they each have more wins than $Y$, contradiction. $\square$ Now return to our problem. Take $X$ with the most losses and $Y$ who beat all $Z$ who beat $X$. An arbitrary player $A\neq X,Y$ falls into one of $3$ different groups: Group 1: $A$ lost to $X,Y$. Group 2: $A$ lost to $Y$ but beat $X$. Group 3: $A$ lost to $X$ and beat $Y$. (Note that it's impossible for $A$ to beat both $X$ and $Y$ by our lemma.) Let there be $a$ members of Group 1, $b$ members of Group 2, and $c$ members of Group 3. So there are $a+b+c+2$ total players. Also $X$ has a record of $(w,l)=(a+c,b+1)$ and $Y$ has a record of $(w,l)=(a+b+1,c)$. We wish to induct downward by removing $X,Y$ and showing that the sum will decrease or stay the same. The only people other than $X,Y$ who will be affected by this removal are those in Group 1; the others won one and lost one so their $w-l$ won't change. Suppose the people in Group 1 are $k_1,k_2,\dots , k_a$. Then we wish to show that \[(a+c-b-1)^3+(a+b+1-c)^3+\sum_{i=1}^a k_i^3\ge \sum_{i=1}^a{(k_i+2)^3}.\]Let $c-b-1=q$. This is equivalent to \[(a+q)^3+(a-q)^3\ge \sum_{i=1}^a{(6k_i^2+12k_i+8)}.\]After simplification this is \[a(a^2+3q^2-4)\ge \sum_{i=1}^a{3((k_i+1)^2-1)}.\]It's not hard to show that $a+q\le k_i\le -(a+q)$, hence $(a+q+1)^2\ge (k_i+1)^2$ and it suffices to show that \[a(a^2+3q^2-4)\ge a(a+q)(a+q+2)\]Miraculously, this simplifies to \[(q-(a+2))(q+1)\ge 0.\]Thank goodness. Anyway, we know that $b\ge c$ because otherwise $X$ would have at least as good of a record as $Y$, then everybody must have the same record, yay equality. So $q\le -1$ and obviously the other factor $c-b-a-3<0$ as well, so the inequality is actually true. Now we are done because the base cases of $n=2,3$ are obvious.
06.04.2015 23:55
The number of edges is $\boxed{ S_1:=\sum w_i = \sum l_i }$. The number of configurations $ A \rightarrow B \rightarrow C $ (in total oder) is $ \sum {{w_i}\choose{2}} = \sum {{l_i}\choose{2}} $ and so $\boxed{S_2:= \sum w_i^2 = \sum l_i^2 }$. The number of configurations $ A \rightarrow B \rightarrow C \rightarrow D $ (in total order) is $ \sum {{l_i}\choose{3}}$, since if we choose $D$ and three vertices that beat $D$, we are assured this configuration will arise. However, $ \sum {{w_i}\choose{3}}$ counts the number of configurations $ A \rightarrow B \rightarrow C \rightarrow D $ and also configurations of the type $ A \rightarrow B,C,D \text{ and } B \rightarrow C \rightarrow D\rightarrow B $. Taking our previous two results into account, this gives $\boxed{T_3:= \sum w_i^3 \ge \sum l_i ^3 =: S_3}$. Now just algebra. Taking into account $ w_i+l_i=n-1=:m $ this gives $\Theta := \sum (w_i-l_i)^3 = \sum (m-2l_i)^3 = -8S_3+12mS_2-6m^2S_1+m^3n \ge -8T_3 + 12mS_2-6m^2S_1+m^3n = \sum (l_i - w_i) ^3 = -\Theta $ and so $ \Theta \ge -\Theta $ so $\boxed{ \Theta \ge 0}$ Q.E.D.
30.08.2015 18:51
Is this solution correct? Let $T$ be the number of quadruples $(P,Q, R, S)$ of people such that $P$ loses against $Q, R,$ and $S$, where $Q, R,$ and $S$ are unordered. $T= \sum {{l_i}\choose{3}}$ (look at $P$ and choose three of the people that $P$ lost against). Since there are no bad companies and $Q, R,$ and $S$ are unordered, we may assume that $Q$ loses against $R$ and $S$ and $R$ loses against $S$. $T\leq \sum {{w_i}\choose{3}}$ (look at $S$ and choose three of the people that $S$ lost against. These can either form a cyclic triple or the triple that we want). $T=\sum {{l_i}\choose{2}}w_i$ (look at $Q$ and chooses one person whom $Q$ won against and two which $Q$ lost against). $T=\sum {{w_i}\choose{2}}l_i$ (look at $R$ and chooses one person whom $R$ lost against and two which $R$ won against). Thus, $\sum {{l_i}\choose{3}}+\sum {{w_i}\choose{2}}l_i=2T\leq\sum {{w_i}\choose{3}}+\sum {{l_i}\choose{2}}w_i$. Using $\sum w_i = \sum l_i$ and $\sum w_i^2 = \sum l_i^2$ and expanding and simplifying, we get $\sum \left(w_i - l_i\right)^3 \geq 0.$
31.08.2015 19:37
Can anyone tell me if my solution is correct? Thanks a lot!
28.11.2015 08:45
Um, it is correct MathPanda1 Nice solution!
28.02.2016 10:08
It is well-known that $\sum w_i = \sum l_i$ and $\sum \binom{w_i}{2} = \sum \binom{l_i}{2}$ (or $\sum w^2_i = \sum l^2_i$) I claim that $\sum \binom{w_i}{3} \ge \sum \binom{l_i}{3}$. By our condition that there are no bad quadruples, for all quadruples $(A,B,C,D)$, if there is a person who lost against the other three, there is a person who won against the other three. This implies that $\sum \binom{w_i}{3} \ge \sum \binom{l_i}{3}$, since the number of quadruples with a person who lost against the other three is $\sum \binom{l_i}{3}$ and the number of quadruples with a person who won against the other three is $\sum \binom{w_i}{3}$. The rest is calculation. We use $w_i+l_i=n-1$ and the discussion above. We have $$\sum w_i = \sum l_i$$$$\sum w^2_i = \sum l^2_i$$$$\sum (w^3_i-3w^2_i+2w_i) = 6\sum \binom{w_i}{3} \ge 6\sum \binom{l_i}{3} = \sum (l^3_i-3l^2_i+2l_i) \implies \sum w^3_i \ge \sum l^3_i$$This gives $$\sum (w_i-l_i)^3 = \sum (2w_i-n+1)^3 = 8\sum w^3_i - 12(n-1)\sum w^2_i + 6(n-1)^2 \sum w_i -\sum(n-1)^3$$$$\ge 8\sum l^3_i - 12(n-1)\sum l^2_i + 6(n-1)^2\sum l_i -\sum (n-1)^3 = \sum (2l_i-n-1)^3 = \sum(l_i-w_i)^3$$which is enough to claim that $\sum (w_i-l_i)^3 \ge 0$, as desired.
08.08.2017 17:23
MathPanda and rkm0959 very good solution.
16.09.2018 23:06
orl wrote: $n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that \[\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.\] Proposed by Sung Yun Kim, South Korea Note that $\sum w_i=\sum \ell_i$ by counting total number of matches, by wins and losses. Counting triples of people that do not form a directed three-cycle, by the person who wins two rounds and again by the person who loses two rounds, we conclude $\sum \binom{w_i}{2} =\sum \binom{\ell_i}{2}$. Let $n=m+1$ and observe that $$\sum (w_i-\ell_i)^3=\sum (w_i^3-\ell_i^3)-3\sum (w_i^2(m-w_i)-\ell_i^2(m-\ell_i))=4 \sum (w_i^3-\ell_i^3)=24 \sum \left( \binom{w_i}{3}-\binom{\ell_i}{3}\right)$$hence it is sufficient to show $\sum \binom{w_i}{3} \ge \sum \binom{\ell_i}{3}$. Consider sets $W$ and $L$ of quadruples of people with one person winning/losing against everyone else. We want $|W| \ge |L|$. Indeed look at any quadruple $(a,b,c,d) \in L$ with $d$ the loser. By our hypothesis, $a,b,c$ do not form a directed cycle so exactly one of them beats the other two. Suppose $a$ beat $b$ and $c$. Now $a$ beats $b,c,d$ so $(a,b,c,d)$ is a quadruple in $W$ with $a$ as the winner. Consequently, we have defined an injective mapping $f: L \mapsto W$ hence $|W| \ge |L|$ as desired. $\blacksquare$ Remark: The only additional elements $W$ has in this case are quadruples $(a,b,c,d)$ with $a$ the winner and $b,c,d$ forming a directed cycle.
29.01.2019 04:38
Really not sure if this is correct... (if anyone can point out my mistake I will be happy ) Claim 1: Let $k>2$. Suppose $V$ is a vertex that loses to only $V_1, V_2, ... , V_k$ then one of $V_1, V_2, ... ,V_k$ must have won against $V$ and $V_1, V_2, ... , V_k$ (excluding itself of course). We prove this by induction on $k$. The $k = 3$ is clear by the hypothesis of the problem. For $k+1$, take $V$ along with $V_1, ... , V_k$. This subgroup must have $V_i$ who has won against $V$ and $V_1, ... , V_k$. Then for the group of $k+1$ vertices to not have a bad tournament, we must have either $V_{k+1}$ with $k+1$ wins or $V_i$ with $k+1$ wins. From claim 1, we can proceed with induction on $n$, and given $V_i$ with $k$ losses and $V_j$ with $k$ wins, we can remove the two with all its edges to reduce the problem to $n-2$.
03.07.2019 04:08
Let $x_{i,j} = 1$ if player $i$ beats player $j$ and -1 otherwise. (Note that $x_{i,j}^2 = 1$.) Then $$\sum^n_{i=1} (w_i - l_i)^3 = \sum^n_{i=1} (\sum_{j\neq i} x_{i,j})^3 = \sum^{i, j \leq n}_{i \neq j} x_{i,j}^3 + 3\sum^{i,j,k \leq n}_{i \neq j \neq k} x_{i,j}^2x_{i,k} + \sum^{i,j,k,l \leq n}_{i \neq j \neq k \neq l} x_{i,j}x_{i,k}x_{i,l}.$$The first term evaluates to $\sum^{i, j \leq n}_{i \neq j} x_{i,j} = 0$, the second term evaluates to $3\sum^{i, j, k \leq n}_{i \neq j \neq k} x_{i,k} = 0$ and the last term is $6\sum^{i,j,k,l \leq n}_{i < j < k < l} (x_{i,j}x_{i,k}x_{i,l} + x_{j,i}x_{j,k}x_{j,l} + x_{k,i}x_{k,j}x_{k,l} + x_{l,i}x_{l,j}x_{l,k}),$ where each term can be checked to be $\geq 0$ as long as $i,j,k,l$ are not a $bad$ company. Hence we are done.
12.01.2020 19:33
Consider the $n\times n$ matrix defined by $a_{i,i}=0$, $a_{i,j}=1$ if $i$ beats $j$, and $-1$ otherwise. Then, we want $$\sum_{i=1}^n\left(\sum_{j=1}^n a_{i,j}\right)^3=\sum_{i=1}^n\left(\sum_{j=1}^n a_{i,j}^3+3\sum_{1\le j\neq k \le n} a_{i,j}a_{i,k}^2 +6\sum_{1\le j\neq k\neq l\le n} a_{i,j}a_{i,k}a_{i,l}\right)$$$$=\sum_{i=1}^n \left((3n-2)\sum_{j=1}^n a_{i,j}+6\sum_{1\le j\neq k\neq l\le n} a_{i,j}a_{i,k}a_{i,l}\right)\ge 0$$Note that $$\sum_{i=1}^n (3n-2)\sum_{j=1}^n a_{i,j}=(3n-2)\sum_{1\le i,j\le n} a_{i,j}=0$$so we just need that $$\sum_{1\le i\neq j\neq k\neq l\le n}a_{i,j}a_{i,k}a_{i,l}\ge 0$$If we consider a set of $4$ people $i,j,k,l$, it is easily verified that $a_{i,j}a_{i,k}a_{i,l}+\ldots +a_{l,i}a_{l,j}a_{l,k}\ge 0$ iff they are not bad. So, summing over all quadruplets of players, we get the desired inequality.
22.03.2020 01:41
Interpret as a tournament on $n$ vertices $v_1,\ldots, v_n$, with a directed edge $v_i\to v_j$ if $v_i$ beats $v_j$. Hence $w_i = \text{outdeg } v_i$ and $l_i = \text{indeg } v_i$. The key to the problem is the following lemmas. The following sums are over all $v\in V$. Lemma 1: In any digraph, $\sum \text{outdeg } v = \sum \text{indeg } v$. Proof: Both count the total number of edges in the graph. $\square$ Lemma 2: In any digraph, $\sum (\text{outdeg } v)^2 = \sum (\text{indeg } v)^2$. Proof: Note that \[ \sum \binom{\text{outdeg } v}{2} = \sum \binom{\text{indeg } v}{2} \]since both count the number of triples of vertices which do not form a 3-cycle. Now we have a quadratic in $\text{outdeg } v$ on the left, and a quadratic in $\text{indeg } v$ on the right, so the result follows. $\square$ Note that in a tournament, $\text{outdeg } v = n-1-\text{indeg } v$ for any vertex $v$. We compute \begin{align*} \sum [\text{outdeg } v - \text{indeg } v]^3 &= \sum [\text{outdeg } v - (n-1-\text{outdeg } v)]^3 \\ &= \sum [(\text{outdeg } v)^3 - (\text{indeg } v)^3] \\ &\qquad - 3\sum (\text{outdeg } v)^2(n-1-\text{outdeg } v) + 3\sum (n-1-\text{indeg } v)(\text{indeg } v)^2 \\ &= \sum [(\text{outdeg } v)^3 - (\text{indeg } v)^3] \\ &\qquad - 3(n-1) \sum (\text{outdeg } v)^2 + 3\sum (\text{outdeg } v)^3 \\ &\qquad + 3(n-1)\sum (\text{indeg } v)^2 - 3\sum (\text{indeg } v)^3 \\ &= 4\sum[(\text{outdeg } v)^3 - (\text{indeg } v)^3] \\ &= 24 \sum \left[ \binom{\text{outdeg } v}{3} - \binom{\text{indeg } v}{3} \right] \end{align*}where the last couple steps follow from the lemmas. In order to show that the above is nonnegative, it suffices to show that there are more quadrupules $(v_i,v_j,v_k,v_{\ell})$ of players where one person beats the other three (call the set of these $A$) than quadruples where one player loses against the other 3 (call the set of these $B$). Suppose $v_i$ loses to $v_j,v_k,v_{\ell}$. By the condition, we know WLOG $v_j$ beats $v_k,v_{\ell}$. Now, $v_j$ has beaten the other three. Therefore, for every element of $B$, there is a corresponding element in $A$; hence $|A|\ge |B|$.
15.09.2020 18:45
Consider a particular set of four players. Let the players be indexed as $i=1,2,3,4$ and for player $i$, let $\mathcal{W}_i,\mathcal{L}_i$ denote their numbers wins and losses respectively. We examine what the multiset $\{\mathcal{W}_i-\mathcal{L}_i\mid i\in\{1,2,3,4\}\}$ can look like. Let the elements of this multiset be $a_i$. Note that $\sum_i a_i=0$ by definition, and there is at most one $i$ such that $a_i=3$ and at most one $i$ such that $a_i=-3$. Note that because $\mathcal{W}_i+\mathcal{L}_i=3$, $a_i\in\{3,1,-1,-3\}$ for each $i$. If at least one $a_i$ is $3$, either all remaining $a_j$ are negative, generating the multiset $\{3,-1,-1,-1\}$, or there exists a remaining positive $a_j$ (which has to be $1$) implying the multiset $\{3,1,-1,-3\}$. A similar argument would hold if there was some $a_i$ equal to $-3$, yielding the multiset $\{1,1,1,-3\}$. If each $a_i\in\{1,-1\}$, then we get the multiset $\{1,1,-1,-1\}$. Now, we aggressively double-count. For convenience, we simply write the number of wins; let $a$ denote the number of companies with internal win numbers of $3,2,1,0$, $b$ the number with win numbers $3111$, $c$ the instances of $2211$, and $d$ the instances of $2220$. By double counting, we have \begin{align*} S_1=\sum \binom{w_i}{3}&=a+b\\ S_2=\sum \binom{w_i}{2}\ell_i&=a+2c+3d\\ S_3=\sum w_i\binom{\ell_i}{2}&=a+2c+3b\\ S_4=\sum \binom{\ell_i}{3}&=a+d. \end{align*}Remark that \[\sum w_i=\sum \ell_i\]and \[\sum (w_i^2-\ell_i^2) = \sum (w_i+\ell_i)(w_i-\ell_i) = (n-1)\sum (w_i-\ell_i) = 0.\]Now, after cancellation, we can write \[\sum (w_i-\ell_i)^3 = \sum w_i^3-\sum \ell_i^3 - 3\left(\sum (w_i^2\ell_i-w_i\ell_i^2)\right) = 6S_1-6S_4 - 3(2S_2-2S_3) = \]\[6(a+b)-6(a+d)-6(a+2c+3d-a-2c-3b) = 6(b-d)+18(b-d) = 24(b-d).\]The desired is now obvious, as $d=0$.
22.09.2020 14:47
redacted
23.09.2020 14:02
The big motivation for this is the question where you count the number of directed triangles by double-counting "angles". Here, instead of counting angles, we count tridents. Take the obvious graph theory interpretation, where $a$ wins $b$ iff there exists an edge directed from $a$ to $b$. We call the subgraph where a vertex $v$ is adjacent to three other vertices a $v$-trident. Say a $v$-trident is of type A, B, C, or D if there are 3, 2, 1, or 0 edges directed out of $v$, respectively. Lemma. $\sum_{i} w_i^2 = \sum_{i} \ell_i^2$. Proof. Since $\sum_i w_i = \sum_i \ell_i$, it suffices to show that $\sum_i \binom{w_i}{2} = \sum_i \binom{\ell_i}{2}$. But this is true by double-counting triangles. Now, we have that $\binom{w_i}{3}$, $\binom{w_i}{2}\ell_i$, $\binom{\ell_i}{2}w_i$, and $\binom{\ell_i}{3}$ are respectively the number of type A, B, C, and D $i$-tridents. Using the lemma and expanding, we have \[6 \sum_i \left(\binom{w_i}{3} - \binom{w_i}{2}\ell_i + \binom{\ell_i}{2}w_i - \binom{\ell_i}{3} \right) = \sum_i (w_i-l_i)^3.\]Let $A,B,C,D$ respectively represent the number of tridents of type A, B, C, and D. Then it suffices to prove that $A-B+C-D \ge 0$. But this is true by summing up over all $K_4$'s in the graph.
02.01.2021 04:08
First of all, notice that we have the identities $\sum w_i = \sum l_i$ and $\sum w_i^2 = \sum l_i^2$, the first by double counting edges and the second by double counting noncyclic triplets. Now, the idea is to count possible outdegrees in four-companies: The possible outdegs are $(2, 2, 1, 1)$, $(3, 2, 1, 0)$, $(3, 1, 1, 1)$, $(2, 2, 2, 0)$, call these types A, B, C, D respectively. Our condition gives us that $D = 0$. Now, consider the following equalities: \begin{align*} \sum \binom{w_i}{3} &= B + C \\ \sum \binom{l_i}{3} &= B \\ \sum w_i \binom{l_i}{2} &= 2A + B + 3C \\ \sum l_i \binom{w_i}{2} &= 2A + B. \end{align*}Notice that \begin{align*} \sum w_i^3 \geq \sum l_i^3 \end{align*}follows from $B + C \geq B$, and notice that \begin{align*} \sum w_i^2l_i \geq \sum w_il_i^2 \end{align*}follows from $2A + B + 3C \geq 2A + B$, thus done after using binomial expansion.
06.01.2021 02:56
Beautiful Problem! Represent the tournament as a directed graph on $n$ vertices as usual. The key observation to be made is that we can characterize any set of $4$ vertices by it's set of outdegrees. That is, the set of outdegrees of any set of $4$ vertices must be one of the following four: \begin{align*} \{0, 1, 2, 3 \} \quad \text{Type \textbf{A}} \\ \{0, 2, 2, 2 \} \quad \text{Type \textbf{B}} \\ \{1, 1, 2, 2 \} \quad \text{Type \textbf{C}} \\ \{1, 1, 1, 3 \} \quad \text{Type \textbf{D}} \end{align*} Lemma: $\sum w_i = \sum \ell_i$ and $\sum w_i^2 = \sum \ell_i^2.$ Proof: The first statement is easy to prove; just note that each edge is both a win and a loss for some team, so thus $$\sum w_i = \sum \ell_i = {n \choose 2}.$$To prove the second statement, note that $$\sum {w_i \choose 2} = \sum {\ell_i \choose 2}$$since both count the number of "non cyclic" triplets in a directed graph. Expanding and using the first property gives the desired $\sum w_i^2 = \sum \ell_i^2.$ Let the number of sets of type $A$ be $a$, and similarly for the others sets. Now I claim the following hold: \begin{align*} a + b &= \sum {\ell_i \choose 3} \\ a + 2c + 3d &= \sum \ell_i {w_i \choose 2} \\ a + 3b + 2c &= \sum w_i {\ell_i \choose 2} \\ a + d &= \sum {w_i \choose 3} \end{align*} The first equation follows from double counting the number of sets of four vertices who have a vertex of outdegree $0$. The second follows from double counting the number of sets of four vertices of have a vertex of outdegree $1,$ and so on. To finish, note that $$d - b = \sum {w_i \choose 3} - {\ell_i \choose 3} \implies 6(d - b) = w_i^3 - \ell_i^3$$and $$3d - 3b = \sum \ell_i {w_i \choose 2} - w_i {\ell_i \choose 2} \implies 18(d - b) = \sum 3 \ell_i w_i^2 - 3 w_i \ell_i^3.$$These follow from our lemmas; Note that \begin{align*}\sum {w_i \choose 3} - {\ell_i \choose 3} &= \sum \frac{w_i(w_i-1)(w_i-2) - \ell_i(\ell_i-1)(\ell_i-2)}{6} \\ &= \sum \frac{w_i^3 - 3w_i^2 + 2w_i - \ell_i^3 + 3 \ell_i^2 - 2\ell_i}{6} \\ &= \sum \frac{w_i^3 - \ell_i^3}{6}\end{align*}and \begin{align*} \sum \ell_i {w_i \choose 2} - w_i {\ell_i \choose 2} &= \frac{w_i^2 \ell_i - w_i \ell_i - \ell_i^2 w_i + w_i \ell_i}{2} \\ &= \frac{w_i^2 \ell_i - \ell_i^2 w_i}{2}. \end{align*} Adding the two gives $24(d-b) = \sum (w_i - \ell_i)^3.$ However, the problem statement gives $b = 0,$ so $\sum (w_i - \ell_i)^3 = 24d \ge 0,$ and we are done.
22.08.2021 06:17
Remark: We can write the desired expression in terms of $w_i$. Then, using standard double counting, we may bash out $\sum \binom{w_i}{k}$ for $k\leq 4$, based on the number of appearances of different configurations of $K_4$. This way, we don't have to think at all (Although I kept messing up the algebra). Note $l_i=n-1-w_i$, so we're alternatively trying to calculate \[\sum_{i=1}^n (2w_i-n+1)^3 = \sum_{i=1}^n 8w_i^3 - 12(n-1) w_i^2 + 6 (n-1)^2 w_i - (n-1)^3\]Note that \[x^3 = 6\cdot \binom{x}{3} + 6 \binom{x}{2} + x \qquad \text{ and } \qquad x^2 = 2\binom{x}{2} +x\]Thus, our desired value is \[ = (48)\sum_{i=1}^n \binom{w_i}{3} + (48-24(n-1))\sum_{i=1}^n \binom{w_i}{2} + (8-12(n-1)+6(n-1)^2)(\sum_{i=1}^n w_i)-n\cdot (n-1)^3\]By inspection, all directed graphs on $K_4$ are of the form $a(3,2,1,0),b(3,1,1,1),c(2,2,2,0),d(2,2,1,1)$. Substituting our values of $a,b,c,d$, this becomes \[=48(a+b) +24(3-n) \frac{4a+3b+3c+2d}{n-3} +(3n^2-12n+18)(n)(n-1)-n(n-1)^3\]\[=48(a+b) -24 (4a+3b+3c+2d) +(3n^2-12n+13)(n)(n-1)-n(n-1)^3\]\[=-48 a - 24 b - 72 c - 48 d + 2n(n-1)(n-2)(n-3)\]\[= 24b-24c\]Since we are guaranteed $c=0$, this is clearly $\geq 0$ and we're done. $\blacksquare$.
25.08.2021 18:31
Solved with a bit of help. All summations are from $1$ to $n$. Consider the obvious directed graph interpretation. First, we have $$\sum w_i^2=\sum l_i^2 \iff \sum (w_i+l_i)(w_i-l_i)=0 \iff (n-1)\sum w_i-l_i=0 \iff \sum w_i=\sum l_i,$$which is clearly true. Now consider the set of the outdegrees for each 4-company. By manual checking (and the fact that no bad companies exist) we find that the only possibilities are $\{3,2,1,0\},\{3,1,1,1\},\{2,2,1,1\}$. Refer to the number of 4-companies of each of these types as $A,B,C$ (respectively). It is clear that we have \begin{align*} \sum \binom{w_i}{3}&=A+B\\ \sum \binom{l_i}{3}&=B\\ \sum w_i\binom{l_i}{2}&=A+3B+2C\\ \sum l_i\binom{w_i}{2}&=A+2C, \end{align*}where all the sums range from $1$ to $n$. Now we have $$A+B \geq B \implies \sum \binom{w_i}{3}-\binom{l_i}{3}\geq 0 \implies \sum w_i^3-l_i^3\geq 0,$$as well as $$A+3B+2C \geq A+2C \implies \sum -l_i\binom{w_i}{2}+w_i\binom{l_i}{2}\geq 0 \implies \sum -l_iw_i^2+w_il_i^2 \geq 0,$$where we use the fact that $\sum w_i-l_i=\sum w_i^2-l_i^2=0$. This is enough imply that $$\sum (w_i-l_i)^3=\sum w_i^3-3w_i^2l_i+3w_il_i^2-l_i^3\geq 0. ~\blacksquare$$
01.09.2021 01:37
Represent this as a tournament. The outdegree and indegree respectively of vertex $v_i$ are $w_i$ and $l_i$, respectively. We are given that for any directed triangle, there is no vertex that loses to all of them. It is well known (by Landau, and also not hard to prove) that $\sum w_i = \sum l_i$ and $\sum w_i^2 = \sum l_i^2$. Note that proving $\sum (w_i - l_i)^3 \geq 0$ is equivalent to proving\begin{align*}\sum [(w_i^3 - l_i^3) - 3w_il_i(w_i - l_i)] &= \sum [w_i^3 - 3w_i^2(n - 1 - w_i) + 3l_i^2(n - 1 - l_i) - l_i^3]\\&= \sum [4(w_i^3 - l_i^3)- 3(n-1)(w_i^2 - l_i^2)]\\&= 4\sum (w_i^3 - l_i^3) \geq 0\end{align*}which is equivalent to showing $\sum w_i^3 \geq \sum l_i^3$. Due to $\sum w_i = \sum l_i$ and $\sum w_i^2 = \sum l_i^2$ this is equivalent to showing $\sum \tbinom{w_i}{3} \geq \sum \tbinom{l_i}{3}$. Note that the former counts the number of pairs $(v, T)$ where $v$ is a person who beats everyone in triple $T$, and the latter counts the number of pairs $(v, T)$ where $v$ is a person who is beaten by everyone in triple $T$. We will prove that for every pair $(v, T)$ of the latter condition, where say $T$ consists of $u_1, u_2, u_3$, we can construct a pair $(v', T')$ from $v, u_1, u_2, u_3$ of the former condition. This induces an injective mapping from the set of the latter type pairs to the set of former type pairs, proving the inequality. Indeed, we know $u_1, u_2, u_3$ must not form a directed cycle so one of these guys beats the two others, along with $v$. Choose this to be $v'$, and let the remaining $3$ be $T'$, and this pair $(v', T')$ is of the former condition, as desired.
04.09.2021 01:13
Let $T$ be the usual tournament of the problem. Take $v \in G$ and let $v_1,v_2,v_3 \in N_{-}(v) \implies$ by the problem's condition, since $v_1v_2v_3$ cannot be an oriented triangle, we have that one of $v_1,v_2,v_3$, say $v_1$ satifies $v,v_2,v_3 \in N_{+}(v)$. This tells us that $$\sum_{i=1}^n \binom{l_i}{3} \leq \sum_{i=1}^{n} \binom{w_i}{3} \quad (*)$$ Now, observe that since $\sum_{i=1}^n w_i = \sum_{i=1}^n l_i$ (well known) $\implies \sum_{i=1}^n (n-1)w_i= \sum_{i=1}^n (n-1)l_i \implies \sum_{i=1}^n (w_i+l_i)w_i= \sum_{i=1}^n (w_i+l_i)l_i \implies \sum_{i=1}^n w_i^2= \sum_{i=1}^n l_i^2. \quad (**)$ Notice that $\sum_{i=1}^n (w_i-l_i)^3 \geq 0 \iff \sum_{i=1}^n (w_i^3-l_i^3)+ 3\sum_{i=1}^n w_il_i(l_i-w_i) \geq 0. \quad (\star)$ From $(*)$ and $(**)$, $\sum_{i=1}^n w_i^3-3w_i^2+2w_i \geq \sum_{i=1}^n l_i^3-3l_i^2+2l_i \implies \sum_{i=1}^n w_i^3 \geq \sum_{i=1}^n l_i^3 \quad (\spadesuit)$ Now, since $\sum_{i=1}^n w_i= \sum_{i=1}^n l_i \implies \sum_{i=1}^n (n-1)^2w_i=\sum_{i=1}^n (n-1)^2l_i \implies \sum_{i=1}^n (w_i+l_i)^2w_i=\sum_{i=1}^n (w_i+l_i)^2l_i \implies \sum_{i=1}^n w_i^3+2w_i^2l_i+w_il_i^2=\sum_{i=1}^n l_i^3+2w_il_i^2+w_i^2l_i \implies$ from $(\spadesuit)$, $0 \leq \sum_{i=1}^n (w_i^3-l_i^3)= \sum_{i=1}^n w_il_i(l_i-w_i) \implies$ from $(\star)$, $\sum_{i=1}^n (w_i^3-l_i^3)+3\sum_{i=1}^n w_il_i(l_i-w_i) \geq 0 \implies \sum_{i=1}^n (w_i-l_i)^3 \geq 0$, as desired. $\blacksquare$
07.12.2021 08:31
Write \(X\to Y\) if \(X\) beat \(Y\). We contend: Claim: We have \[\sum_{i=1}^nw_i=\sum_{i=1}^n\ell_i\quad\text{and}\quad \sum_{i=1}^n\binom{w_i}2=\sum_{i=1}^n\binom{\ell_i}2.\] Proof. The first counts the number of edges in the graph, and the latter counts the number of triples of vertices \((A,B,C)\) where \(A\to B\) and \(B\to C\). \(\blacksquare\) Claim: We have \[\sum_{i=1}^n\binom{w_i}3\ge\sum_{i=1}^n\binom{\ell_i}3.\] Proof. The term \(\sum_{i=1}^n\binom{w_i}3\) counts the number of winning quadruples \((A,B,C,D)\) where \(A\to B\), \(A\to C\), \(A\to D\), and (without loss of generality) \(B\to C\) and \(C\to D\), The term \(\sum_{i=1}^n\binom{\ell_i}3\) counts the number of losing quadruples \((A,B,C,D)\) where \(A\to D\), \(B\to D\), \(C\to D\) and (without loss of generality) \(A\to B\) and \(B\to C\). Since there are no bad companies, in each losing quadruple \((A,B,C,D)\) we must have \(A\to C\), implying that each losing quadruple is also a winning quadruple. The claim follows. \(\blacksquare\) It readily follows that \[\sum_{i=1}^nw_i=\sum_{i=1}^n\ell_i,\quad \sum_{i=1}^nw_i^2=\sum_{i=1}^n\ell_i^2,\quad \sum_{i=1}^nw_i^3\ge\sum_{i=1}^n\ell_i^3.\]Then since \(w_i+\ell_i=n-1\) always, we have \begin{align*} \sum_{i=1}^n(w_i-\ell_i)^3 &=\frac12\left[\sum_{i=1}^n\big(w_i-(n-1-w_i)\big)^3-\sum_{i=1}^n\big(\ell_i-(n-1-\ell_i)\big)^3\right]\\ &=\frac12\left[\sum_{i=1}^n\big(2w_i-(n-1)\big)^3-\sum_{i=1}^n(2\ell_i-(n-1))^3\right]\\ &=4\left(\sum_{i=1}^nw_i^3-\sum_{i=1}^n\ell_i^3\right)\ge0, \end{align*}as desired.
22.10.2022 08:04
This solution isn't that nice, but that's alright. Use the obvious tournament interpretation; all sums are over all vertices $i$. Note that $w_i + \ell_i = n-1$, so $w_i-\ell_i = n-1-2\ell_i$. Let $a$ be the number of groups of $4$ that have outdegrees $(3,2,1,0)$, $b$ the number of groups that have outdegrees $(3,1,1,1)$, $c$ the number of groups that have outdegrees $(2,2,1,1)$, and $d$ the number of groups that have outdegrees $(2,2,2,0)$. (Note $d=0$.) We write \begin{align*} \sum_i (w_i-\ell_i)^3 &= \sum_i (n-1-2\ell_i)^3 = (n-1)^3 - 2(n-1)^2 \ell + 4(n-1)\ell^2 - 8\ell^3\\ & = \sum_i (n-1)^3 - 2(n-1)^2 \binom \ell 1 + 4 (n-1) \left(2\cdot \binom \ell 2 + \binom\ell 1 \right) - 8\cdot \left(6\cdot \binom \ell 3 + 6\cdot \binom \ell 2 + 8\binom \ell 1\right)\\ & = \sum_i (n-1)^3 - (6n^2-24n+26) \binom \ell 1 + 24(n-3)\binom \ell 2 - 48 \binom \ell3\\ \end{align*} Now, observe the following: $\sum_i \ell_i = \text{\# edges} =\frac{n(n-1)}{2}$. $\sum_i(n-3)\binom \ell2$ is the number of ways to choose a vertex $v$, two edges that point towards it, and one other arbitrary edge coming out from it. Each set counted in $a$ contributes $\binom 32 + \binom 22$ to this sum, each set counted in $b$ contributes $3\cdot \binom22$, each set in $c$ contributes $2\cdot \binom 22$, and each set in $d$ contributes $\binom 32$. $\sum_i \binom \ell3$ is the number of ways to choose a vertex $v$ and three edges that point towards it. This is $a+d$. Using these, we have that \begin{align*}\sum_i(w_i-\ell_i)^3 & = \sum_i (n-1)^3 - (6n^2-24n+26) \binom \ell 1 + 24(n-3)\binom \ell 2 - 48 \binom \ell3\\ & = n(n-1)^3 - (3n^2-12n+13)(n)(n-1) + 24(4a+3b+2c+3d) - 48(a+d)\\ & = 48(a+b+c+d) + 24b - 24 d - 2n(n-1)(n-2)(n-3)\\ & = 48\binom n4 + 24b - 24 d - 48 \binom n4\\ & = 24(b-d) \geq 0, \end{align*}as desired.
27.01.2023 06:54
Let $a$ be the number of four-element subsets of the players with outdegrees $\{3, 2, 1, 0\}$, $b$ be the number of subsets with outdegrees $\{3, 1, 1, 1\}$, and $c$ be the number of subsets with outdegrees $\{2, 2, 1, 1\}$. It follows that \begin{align*} \sum_{i=1}^n {w_i \choose 3} &= a+b \\ \sum_{i=1}^n {\ell_i \choose 3} &= a \\ \sum_{i=1}^n \ell_i{w_i \choose 2} &= a+2c \\ \sum_{i=1}^n w_i {\ell_i \choose 2} &= a+3b+2c. \end{align*}Furthermore, notice that $$\sum_{i=1}^n {\ell_i \choose 2} = \frac{4a+3b+2c}{n-3} = \sum_{i=1}^n {w_i \choose 2}$$again by double counting in the obvious way. As a result, we have that the sum of the squares of the $w_i$ and the $\ell_i$ are equal. This means that the desired sum $$\sum_{i=1}^n (w_i-\ell_i)^3 = 6\left[{w_i \choose 3} - {\ell_i \choose 3} + w_i{\ell_i \choose 2} - \ell_i{w_i \choose 2}\right] =a+b-a-a-2c+a+3b+2c=4b \geq 0,$$as needed.
17.08.2023 21:37
We claim that $$\sum_{i = 1}^{n} {w_i \choose 2} = \sum_{i=1}^{n} {\ell_i \choose 2}$$The LHS counts the number of triplets where one person has $2$ wins and the RHS counts the number of triplets where one person has $0$ wins. These are the same thing so the equality is proved. Now, using the fact that $$\sum_{i=1}^n w_i = \sum_{i=1}^n \ell_i$$we have $$\sum_{i=1}^n w_i^2 = \sum_{i=1}^n \ell_i^2$$Now note that $$\sum^n_{i=1} \left(w_i - \ell_i\right)^3 = \sum_{i=1}^n w_i^3 - \sum_{i=1}^n \ell_i^3$$due to how everything else cancels out. Therefore it simply suffices to prove that $$\sum_{i=1}^n {w_i \choose 3} \ge \sum_{i=1}^n {\ell_i \choose 3}$$The LHS counts the number of groups of four where the win count for each person is $(3, 1, 1, 1)$ or $(3, 2, 1, 0)$ while the RHS counts the number of groups of four where the win count for each person is $(3,2,1,0)$ and $(2,2,2,0)$. Notice that there does not exist a $(2,2,2,0)$ so we are done.
07.09.2023 01:54
Again, peak of global problems This one's one of my favorite problems
10.10.2023 04:38
We will use the identity $$x^3=6{x\choose 3}+3x^2-2x.$$Thus, it suffices to show that $$6\sum {w_i\choose 3}+3\sum w_i^2 - 2 \sum w_i\geq 6\sum {\ell_i\choose 3}+3\sum \ell_i^2 - 2 \sum \ell_i.$$Clearly, $$\sum w_i=\sum \ell_i.$$Furthermore, it is a well known property of a tournament that $$\sum w_i^2=\sum \ell_i^2.$$Thus, it suffices to show that $$\sum{w_i\choose 3}\geq \sum {\ell_i\choose 3}.$$ Another interpretation of $\sum{w_i\choose 3}$ is the number of groups of 4 players for which some player beat all the other three players. We call these winner groups. Similarly, $\sum{\ell_i\choose 3}$ is the number of groups of 4 players for which some player lost to all three other players, which we call loser groups. Claim: Any loser group is also a winner group. Suppose the players are $A,B,C,D$, and say that $A$ lost to $B,C,D$. Note that $\triangle BCD$ cannot be a cycle, since otherwise $ABCD$ will be a bad company. Hence, one of $B,C$, or $D$ beat the other two, and thus it is also a winner group. Thus, there are at least as many winner groups as loser groups, hence done.
22.11.2023 10:15
First we will characterize all the types of matches that can occur. Let $(w, x, y, z)$ denote the number of wins that the four players could have amongst each other. Let $A$ denote the number of companies of the form $(3, 2, 1, 0)$ Let $B$ denote the number of companies of the form $(3, 1, 1, 1)$ Let $C$ denote the number of companies of the form $(2, 2, 2, 0)$ Let $D$ denote the number of companies of the form $(2, 2, 1, 1)$ Each of these sets of wins contribute exactly one complete, directed graph, on $4$ vertices, ie: one possibility. Now we make some observations. Observe that, \begin{align*} \sum_i w_i = \sum_i \ell_i \end{align*}as in each game there is exactly one winner and one loser. Next note we clearly have, \begin{align*} \sum_i w_i^2 = \sum_i \ell_i^2 \end{align*}To see this consider manipulating the expression as follows, \begin{align*} \sum_i w_i^2 - \sum_i \ell_i^2 &= \sum_i (w_i^2 - \ell_i^2)\\ &= \sum_i (w_i + \ell_i)(w_i - \ell_i)\\ &= \sum_i 2n(w_i - \ell_i) = 2n \cdot \left(\sum_i w_i - \sum_i \ell_i \right) = 0 \end{align*}Now we are ready to proceed with the desired statment. Note we have \begin{align*} S = \sum_i (w_i-\ell_i)^3 &= \sum_i w_i^3 - \sum_i 3w_i^2\ell + \sum_i 3w_i\ell_i^2 - \sum_i \ell_i^3 \end{align*}Now for the key manipulation. Noting that terms of the form $\sum_i w^2 - \sum_i \ell^2$ and $\sum_i w_i - \sum \ell_i$ vanish we can rewrite the terms as follows, \begin{align*} S = 6 \sum_i \binom{w_i}{3} - 6 \sum_i \binom{w_i}{2} \ell_i + 6 \sum_i w_i \binom{\ell_i}{2} - 6\sum_i \binom{\ell_i}{3} \end{align*}Now we can find neater combinatorial representations of the sums. The first term, $6 \sum_i \binom{w_i}{3}$ counts $6$ times the triples of players $(x, y, z)$ such that a player $p$ beat $x$, $y$ and $z$, over all players $p$ and triples $(x, y, z)$. Note that then this sum is simply $6A + 6B$. Next note that, $6 \sum_i \binom{w_i}{2} \ell_i$ counts $6$ times the number of triples $(x, y, z)$ such that a player $p$ won against $x$ and $y$ and lost to $w$ over all players $p$ and triples $(x, y, z)$. Clearly this is simply $6A + 18C + 12D$. Similarly, we present a similar argument for $6 \sum_i w_i \binom{\ell_i}{2}$. It counts all triples $(x, y, z)$ such that a player $p$ won against $x$ and lost against $y$ and $z$. Then we find that this is simply $6A + 18B + 12D$. Finally, $6 \sum_i \binom{\ell_i}{3}$ counts the $6$ times the number of triples of the form $(x, y, z)$ where a player $p$ lost to $x$, $y$ and $z$, over all players $p$ and all triples $(x, y, z)$. This is simply $6A + 6C$. Our final sum is then, \begin{align*} S &= (6A + 6B) - (6A + 18C + 12D) + (6A + 18B + 12D) - (6A+6C)\\ &= 24B - 24C \end{align*}However the $C$ term characterizes all bad companies, so it vanishes leaving us with $S = 24B \geq 0$ as desired.
28.11.2023 21:56
Let $a_{ij}=1$ if $i$ beat $j$ and $-1$ otherwise. Note that $a_{ij}=-a_{ji}$. Define $a_{ii}=0$. We have \begin{align*} & \sum_{i=1}^{n} (w_i-l_i)^3 \\ =& \sum_{i=1}^{n} \left(\sum_{j=1}^{n}a_{ij}\right)^3 \\ =& \sum_{i=1}^{n} \left( \sum_{a=1}^{n}a_{ia}^3 + 3\sum_{1\le a,b\le n,a\ne b}^{n}a_{ia}^2 a_{ib} + 6\sum_{1\le a<b<c\le n}^{n}a_{ia} a_{ib} a_{ic} \right) \\ =& \sum_{i=1}^{n} \left( \sum_{a=1}^{n}a_{ia} + 3\sum_{1\le a,b\le n,a\ne b,a\ne i}^{n}a_{ib} + 6\sum_{1\le a<b<c\le n}^{n}a_{ia} a_{ib} a_{ic} \right) \\ =& 3\sum_{i=1}^{n}\sum_{1\le a,b\le n,a\ne b,a\ne i}^{n}a_{ib} +6\sum_{i=1}^{n}\sum_{1\le a<b<c\le n}^{n}a_{ia} a_{ib} a_{ic} \\ =& 3\sum_{i=1}^{n}(n-2)a_{ib} +6\sum_{i=1}^{n}\sum_{1\le a<b<c\le n}^{n}a_{ia} a_{ib} a_{ic} \\ =& \sum_{1\le a,b,c,i\le n,\text{they are all distinct}}^{n}\left(\sum_{\text{cyc}}a_{ia} a_{ib} a_{ic}\right).\end{align*}The "no bad company" condition finishes. $\blacksquare$
10.12.2023 18:56
For any $4$ players the only 'acceptable' combinations of wins are $3210$, $2211$, and $3111$, where the $n$th number in this sequence corresponds to the number of wins against the other $3$ players for the $n$th player. Let the number of $3210$s be $A$, and $3111$s be $B$, and $2211$s be $C$. Expanding \[\sum^n_{i=1} \left(w_i - \ell_i\right)^3 \geq 0\]we have \[\sum^n_{i=1} w_i^3 - 3w_i^2{\ell_i} + 3w_i{\ell_i^2} -\ell_i^3\geq 0\]We know that \[\sum^n_{i=1} w_i = \sum^n_{i=1} \ell_i\]and that \[\sum^n_{i=1} w_i^2 = \sum^n_{i=1} \ell_i^2\] so it follows that saying \[\sum^n_{i=1} w_i^3 - \ell_i^3 \geq 0\]is equivalent to saying that \[\sum^n_{i=1} \binom{w}{3} - \binom{\ell}{3} \geq 0\](by expanding and setting terms equal to each other). Then $\binom{w}{3}$ 'corresponds' to $A + B$(due to presence of a person winning $3$ games, and the $\binom{\ell}{3}$ corresponds to $A$, due to the presence of a person losing all games. So, our full expression adds up to $B$. $\newline$ We then notice that \[\sum^n_{i=1} 3w_i^2{\ell_i} - 3w_i{\ell_i^2} \geq 0\]is equivalent to saying that \[\sum^n_{i=1} w_i{\binom{\ell_i}{2}} - \ell_i{\binom{w_i}{2}} \geq 0\]. We can combinatorically interpret this as as the number of players that beat one player in a group of $3$ and lose to the others, minus the number of players that beat two players and lose to the others. This is equal to $A + 3B + 2C - A - 2C = 3B$. Summing up everything, we get $3B + B = 4B$, which is clearly greater than $0$, so we are finished.
11.06.2024 03:11
Notice each group of $4$ players can have indegree multiset: \[\{3,2,1,0\}\text{, }\{3,1,1,1\}\text{, }\{2,2,1,1,\}\text{, or }\{2,2,2,0\}\]Let $a,b,c,d$ be the amount of each $4$ player multiset we can find in our tournament. Now using the in/out degree of each vertex to count these multisets we get \[\sum_{i = 1}^n {w_i \choose 3} = a+b \text{, } \sum_{i = 1}^n {w_i \choose 2}{\ell_i \choose 1} = a+c+d \text{, } \sum_{i = 1}^n {w_i \choose 1}{\ell_i \choose 2} = a+b+c \text{, and } \sum_{i = 1}^n {\ell_i \choose 3} = a+d\]The middle two equations gives \[\sum_{i = 1}^n 3w_i\ell_i^2-3w_i^2\ell_i = 6(b-d)\]Furthermore, properties of tournaments gives \[\sum_{i = 1}^n w_i = \sum_{i = 1}^n \ell_i \text{ and } \sum_{i = 1}^n w_i^2 = \sum_{i = 1}^n \ell_i^2\]where the second one follows from counting groups of $3$ players that aren't cycles. Therefore, using the 1st and 4th, this implies \[\sum_{i = 1}^n w_i^3 - \ell_i^3 = 6(b-d)\]Therefore, \[\sum_{i = 1}^n (w_i-\ell_i)^3 = 12(b-d) \ge 0\]since $d = 0$ from the weird condition the problem gives us.
10.08.2024 20:07
For any group of $4$ people, the out degree set (out degree meaning number of wins) is either $$(0,2,2,2), (0,1,2,3), (1,1,2,2), (1,1,1,3),$$(let the number total number of sets of $4$ people in these classes be $A, B, C,D$, respectively). For any set of $3$ people that person $i$ won against, these four people would either be in class $B$ or $D$. Since each group in class $B$ or $D$ produces exactly one of these $i$ and $3$ people sets, we know $$\sum_{i=1}^n \binom{w_i}{3} = B+D.$$Similarly, $$\sum_{i=1}^n \binom{l_i}{3} = A+B.$$For any set of $2$ people that $i$ wins against, joined with the set of any person that $i$ loses against, these $4$ people is either in class $A,B,C.$ For any group in class $A,B,$ and $C,$ they produce $3,1$ and $2$ of these sets, respectively. Hence, $$\sum_{i=1}^n \binom{w_i}{2} \binom{l_i}{1} = 3A+B+2C.$$Similarly, $$\sum_{i=1}^n \binom{w_i}{1} \binom{l_i}{2} = B+2C+3D.$$After expanding these binomials, we eventually get $$\sum_{i=1}^n (w_i-l_i)^3 = 24D-24A + \sum_{i=1}^n (3w_i^2-2w_i-3l_i^2+2l_i).$$Since $$\sum_{i=1}^n (w_i-l_i) = 0$$and $$\sum_{i=1}^n (w_i^2-l_i^2) = \sum_{i=1}^n (w_i+l_i)(w_i-l_i) = (n-1) \sum_{i=1}^n (w_i-l_i)=0,$$we get $$\sum_{i=1}^n (w_i-l_i)^3=24D-24A=24D \ge 0,$$and we are done. \qed
22.08.2024 03:24
(Used ARCH hints) but motivation where ;-; Rating (MOHs): 30
Attachments:

11.09.2024 21:20
It is easy to check that all we need to prove is \[\sum_i w_i^3 \geq \sum_i \ell_i^3 \iff \sum_i \binom{w_i}3 \geq \sum_i \binom{\ell_i}3\]This is just because of the well known/easy to see facts that $\bullet$ $\sum_i w_i=\sum_i \ell_i$. $\bullet$ $\sum_i w_i^2=\sum_i \ell_i^2$. Now we will count combinatorial harmonic bundles of players $(A,B,C,D)$ (hehe) where $\bullet$ $A$ beats $B$, $C$, $D$. $\bullet$ $D$ is beaten by $B$, $C$. $\bullet$ $B$ beats $C$. Fix $D$, now see that the bundles associated to $D$ is exactly $\binom{\ell}3$ where $\ell$ is the number of games it lost because if $A$, $B$ $C$ are any $3$ players who won against $D$, they cannot form a rock, paper, scissors type of matchup among them three (basically each player won one game and lost one exactly) or else there is a bad company. Hence the total number of these bundles is exactly \[\sum_i \binom{\ell_i}3\]Now if we fix $A$, then the total number is just upperbounded by any $3$ people who lost against $A$, which is exactly $\binom{w}3$, where $w$ is the number of wins $A$ had and hence the total number of bundles is atmost \[\sum_i \binom{w_i}3\]And so we get that \[\sum_i \binom{w_i}3 \geq \sum_i \binom{\ell_i}3\]as desired.