Se trata de un torneo (dibujar una flecha desde $i$ a $j$ siempre que $a_{ij}=r$ ) y quiere demostrar que su suma es maximizada para un torneo acíclico $AC_n$ .
Denota por $\deg(i)$ el grado de salida de $i$ . Entonces $$\prod_{i\in X,j\notin X}a_{ij}=r^{-\binom{k}2}\prod_{i\in X} r^{\deg(i)}=f\left(\sum_{i\in X}\deg(i)\right)$$ para una función convexa $$f(t)=r^{-\binom{k}2+t}.$$
Afirmo que dicha suma se maximiza en $AC_n$ para cualquier función convexa $f$ . En otras palabras, si asociamos a nuestro torneo $T_n$ el multiconjunto $M_k(T_n)$ de $\binom{n}k$ números $\sum_{i\in X}\deg(i)$ , donde $X$ se pasa por encima $k$ -subconjuntos de $\{1,\dots,n\}$ entonces $M_k(AC_n)$ se especializa $M_k(T_n)$ .
Al principio, lo establecemos para $k=1$ . Este caso significa que el conjunto de grados de $T_n$ es mayoritaria por el conjunto múltiple $\{0,1,\dots,n-1\}$ (grados de $AC_n$ ). De hecho, para cualquier $m=1,\dots,n$ la suma de grados de cualquier $m$ vértices de $T_n$ es al menos $\binom{m}2=0+1+\dots+(m-1)$ (ya que la suma de grados es al menos el número de aristas entre estos $m$ vértices). Esto significa (por la propia definición), que el conjunto de grados de $T_n$ es mayoritaria en $0,1,\dots,n-1$ .
Ahora basta con demostrar que si un conjunto múltiple $A=\{a_1,\dots,a_N\} $ mayoriza otro multiconjunto $B=\{b_1,\dots,b_N\}$ entonces lo mismo ocurre con su $k$ -suma en sentido estricto (sin repeticiones): $a_{i_1}+\dots+a_{i_k}$ , $i_1<\dots<i_k$ ). Se deduce de la siguiente observación: $B$ se obtiene de $A$ mediante una secuencia de movimientos "toma dos elementos desiguales y los une con la suma que se fija". Cada uno de estos movimientos corresponde a cambios similares del conjunto múltiple de $k$ -sumas.
