17th Mexico 2003 Problem A3 At a party there are n women and n men. Each woman likes r of the men, and each man likes r of then women. For which r and s must there be a man and a woman who like each other?
r + s > n Solution Consider the number of pairs (W,M), where W is a woman and M a man. If no pair like each other, then the nr pairs (W,M) where W likes M and the ns pairs (W,M), where M likes W must all be distinct. But the total number of available pairs is n 2 , so we must have nr + ns ≤ n 2 and hence r + s ≤ n. Conversely, suppose r + s ≤ n. Label the women W 1 , W 2 , ... , W n and the men M 1 , M 2 , ... , M n . Let woman W i like men M i+k for k = 0, 1, 2, ... , r-1, and let man M i like women W i+k for k = 1, 2, ... , s (we use the cyclic subscript convention, so W n+1 means W 1 etc). Then it is clear that no woman and man like each other. 17th Mexican 2003 © John Scholes jscholes@kalva.demon.co.uk 1 March 2004 Last corrected/updated 1 Mar 04