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 () pairs. Let denote the set . Let be the number of roses presented by the husband from the -th pair to the wife from the -th pair. By condition, the wife from the -th pair will be offended if
On the other hand, for any there exists a partition of such that and
Since each belongs either to or to , we have . Now from (2) it follows that
If we suppose that there are no offended wives then from (1) it follows that
From (3) and (4) it follows that
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.