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.
Problem
Source:
Tags: combinatorics
x3yukari
16.09.2021 14:24
Suppose at the end, after pairing all possible boys and girls, there is at least one girl and one boy that are not friends. Each boy left must be friends with at least one girl in the entire group. Now all of the girls he is friends with must have been left with no option but to go to a different guy, implying those different boys were left with only those girls, either because they only have those girls as friends, or because all other girls they are friends with have to go with other different boys. This implies that those other different boys either have only those girls as friends or because all other girls with have to go with yet another set of different boys. Since this has to end at some point, after pairing all of these mentioned boys with girls again, this results in for some $n$, $n-1$ girls are the only friend of at least $n$ boys, contradiction.