Maths Olympiad Prep

Library / /18 of 24

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Belarus

Some family pairs are friends with each other. Every St. Valentine's Day each husband of these pairs presents some roses to each wife of these pairs (including his own wife). Any wife will be offended by her husband if the number of roses that she obtains from her husband is less than or equal to the number of roses that he presents to all other wives together. This year, it turned out, that for any wife there is a partition of all husbands into two groups such that the total numbers of roses that are presented to this wife by the men from each group are equal (the groups may be different for different women).
Prove that at least one wife will be offended.

Solution

Consider nn (n2n \ge 2) pairs. Let MM denote the set {1,2,...,n}\{1, 2, ..., n\}. Let aija_{ij} be the number of roses presented by the husband from the ii-th pair to the wife from the jj-th pair. By condition, the wife from the jj-th pair will be offended if
ajjiM{j}aji.(1) a_{jj} \le \sum_{i \in M \setminus \{j\}} a_{ji}. \quad (1)
On the other hand, for any jMj \in M there exists a partition of MM such that M=Mj1Mj2M = M_j^1 \cup M_j^2 and
iMj1aij=iMj2aijjM.(2) \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 jMj \in M belongs either to Mj1M_j^1 or to Mj2M_j^2, we have iMj1aij=iMj2aijajj\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
iMaij=iMj1aij+iMj2aij2ajjjM.(3) \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
2ajj>iM{j}aji+ajj=iMajijM.(4) 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
2jMajjjMiMaij=iMjMaij<2iMaii. 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.