Browse · MathNet
PrintFinal Round
Belarus counting and probability
Problem
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.
Techniques
Counting two waysLinear and quadratic inequalities