Skip to main content
OlympiadHQ

Browse · MathNet

Print

XIII OBM

Brazil counting and probability

Problem

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.

Techniques

Coloring schemes, extremal arguments