At a party every woman dances with at least one man, and no man dances with every woman. Show that there are men and and women and such that dances with , dances with , but does not dance with , and does not dance with .
Solution
Let be one of the men who dance with the maximal number of women, one of the women he doesn't dance with, and one of the men dances with. If were to dance with every woman that dances with, then the maximality of the number of women that dances with would be contradicted, so there is a woman that dances with but not with , and we're done.
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.