Let $n>k$ be positive integers, $r>1$ a positive real number, and $A=\{1,2,\dots,n\}$. For $1\leq i\neq j\leq n$, let $a\_{i,j}\in\{r,1\}$ be such that $a\_{i,j}=r\Leftrightarrow a\_{j,i}=1$. Consider the sum
$$S=\sum\_{X\subseteq A, |X|=k}\prod\_{i\in X, j\in A\backslash X}a\_{i,j}.$$


Is it true that $S$ is maximized when $a\_{i,j}=r$ for all $i<j$?


Observe that the number of ordered pairs $(i,j)$ such that $a\_{i,j}=r$ is fixed (i.e. half of all the pairs); the same holds for $a\_{i,j}=1$. Therefore it should be optimal to group as many terms equal to $r$ as possible in the same product. 



Maximize sum of products of binary variable
We deal with a tournament (draw an arrow from $i$ to $j$ whenever $a\_{ij}=r$) and want to prove that your sum is maximized for an acyclic tournament $AC\_n$. 


Denote by $\deg(i)$ the out-degree of $i$. Then
$$\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)$$ 
for a convex function $$f(t)=r^{-\binom{k}2+t}.$$


I claim that such a sum is maximized on $AC\_n$ for *any* convex function $f$. In other words, if we associate with our tournament $T\_n$ the multiset $M\_k(T\_n)$ of $\binom{n}k$ numbers $\sum\_{i\in X}\deg(i)$, where $X$ runs over $k$-subsets of $\{1,\dots,n\}$, then $M\_k(AC\_n)$ [majorizes](https://en.wikipedia.org/wiki/Majorization) $M\_k(T\_n)$.


At first, we establish this for $k=1$. This case means that the multiset of degrees of $T\_n$ is majorized by the multiset $\{0,1,\dots,n-1\}$ (degrees of $AC\_n$). Indeed, for any $m=1,\dots,n$, the sum of degrees of any $m$ vertices of $T\_n$ is at least $\binom{m}2=0+1+\dots+(m-1)$ (since the sum of degrees is at least the number of edges between these $m$ vertices). This means (by the very definition), that the multiset of degrees of $T\_n$ is majorized by $0,1,\dots,n-1$.


Now it suffices to prove that if one multiset $A=\{a\_1,\dots,a\_N\} $ majorizes another multiset $B=\{b\_1,\dots,b\_N\}$, then the same holds for their $k$-wise sums (without repetitions: $a\_{i\_1}+\dots+a\_{i\_k}$, $i\_1<\dots<i\_k$). It follows from the following observation: $B$ is obtained from $A$ by a sequence of moves 'take two unequal elements and bring them together with the sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.


