Track / Stage 4 / 180 of 340 #1080 of 2604

Problem 1080

AMC 12 late, AIME early

Combinatorics Difficulty 4.8 Prove it Brazilian Mathematical Olympiad · Brazil

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$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $M$ be one of the men who dance with the maximal number of women, $W'$ one of the women he doesn't dance with, and $M'$ one of the men $W'$ dances with. If $M'$ were to dance with every woman that $M$ dances with, then the maximality of the number of women that $M$ dances with would be contradicted, so there is a woman $W$ that dances with $M$ but not with $M'$ , and we're done.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.