Question 7
There are $m$ girls and $n$ boys, $m,n\ge2$, taking part in a duet festival. Each session presents one program. A program consists of male–female duets, with each girl–boy pair singing at most one song and every student singing at least one song. Two programs are different if some girl–boy pair sings in one program but not the other. The festival ends only after every possible different program has been performed exactly once.
a) A program is called dependent on student $X$ if canceling all duets involving $X$ leaves at least one other student singing no song in that program. Prove that among all programs dependent on $X$, the number with an odd number of songs equals the number with an even number of songs.
b) Prove that the organizers can order the sessions so that any two consecutive sessions have different parities of their numbers of songs.
a) A program is called dependent on student $X$ if canceling all duets involving $X$ leaves at least one other student singing no song in that program. Prove that among all programs dependent on $X$, the number with an odd number of songs equals the number with an even number of songs.
b) Prove that the organizers can order the sessions so that any two consecutive sessions have different parities of their numbers of songs.