Problem

Source:

Tags: combinatorics



In a dance class there are $10$ boys and $10$ girls. It is known that for each $1\le k\le 10$ and for each group of $k$ boys, the number of girls who are friends with at least one boy in the group is not less than $k$. Prove that it is possible to pair up the boys and the girls for a dance so that each pair consists of a boy and a girl who are friends.