Problem

Source: Dutch IMO TST 2016 day 3 p1

Tags: combinatorics



Let $n$ be a positive integer. In a village, $n$ boys and $n$ girls are living. For the yearly ball, $n$ dancing couples need to be formed, each of which consists of one boy and one girl. Every girl submits a list, which consists of the name of the boy with whom she wants to dance the most, together with zero or more names of other boys with whom she wants to dance. It turns out that $n$ dancing couples can be formed in such a way that every girl is paired with a boy who is on her list. Show that it is possible to form $n$ dancing couples in such a way that every girl is paired with a boy who is on her list, and at least one girl is paired with the boy with whom she wants to dance the most.