Boys and girls in a party
Source: Problem 1, Brazilian MO, 1991
March 19, 2006
combinatorics proposedcombinatorics
Problem Statement
At a party every woman dances with at least one man, and no man dances with every woman. Show that there are men M and M' and women W and W' such that M dances with W, M' dances with W', but M does not dance with W', and M' does not dance with W.