Belarus — Final Round

Consider $n$ ($n \ge 2$) pairs. Let $M$ denote the set $\{1, 2, ..., n\}$. Let $a_{ij}$ be the number of roses presented by the husband from the $i$-th pair to the wife from the $j$-th pair. By condition, the wife from the $j$-th pair will be offended if
$$a_{jj} \le \sum_{i \in M \setminus \{j\}} a_{ji}. \quad (1)$$
On the other hand, for any $j \in M$ there exists a partition of $M$ such that $M = M_j^1 \cup M_j^2$ and
$$\sum_{i \in M_j^1} a_{ij} = \sum_{i \in M_j^2} a_{ij} \quad \forall j \in M. \quad (2)$$
Since each $j \in M$ belongs either to $M_j^1$ or to $M_j^2$, we have $\sum_{i \in M_j^1} a_{ij} = \sum_{i \in M_j^2} a_{ij} \ge a_{jj}$. Now from (2) it follows that
$$\sum_{i \in M} a_{ij} = \sum_{i \in M_j^1} a_{ij} + \sum_{i \in M_j^2} a_{ij} \ge 2a_{jj} \quad \forall j \in M. \quad (3)$$
If we suppose that there are no offended wives then from (1) it follows that
$$2a_{jj} > \sum_{i \in M \setminus \{j\}} a_{ji} + a_{jj} = \sum_{i \in M} a_{ji} \quad \forall j \in M. \quad (4)$$
From (3) and (4) it follows that
$$2 \sum_{j \in M} a_{jj} \le \sum_{j \in M} \sum_{i \in M} a_{ij} = \sum_{i \in M} \sum_{j \in M} a_{ij} < 2 \sum_{i \in M} a_{ii}.$$
The obtained contradiction yields that there exists at least one offended wife.