Question 169
Let $n$ be a positive integer. In a village live $n$ boys and $n$ girls. For the annual ball, $n$ dance couples must be formed, each consisting of one boy and one girl. Each girl submits a list consisting of the name of the boy with whom she would most like to dance, plus zero or more names of other boys with whom she would also be willing to dance. It turns out that $n$ dance couples can be formed such that every girl dances with a boy who is on her list.
Prove that it is possible to form $n$ dance couples such that every girl dances with a boy who is on her list and such that at least one girl dances with the boy with whom she would most like to dance.
Prove that it is possible to form $n$ dance couples such that every girl dances with a boy who is on her list and such that at least one girl dances with the boy with whom she would most like to dance.