MathDB

10 boys and 10 girls in a dance class Puerto Rico Ibero TST 2010.5

Source:

September 16, 2021

combinatorics

Problem Statement

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.