MathDB

There are

m

boys and

n

girls participate in a duet singing contest (

m,n\geq 2

). At the contest, each section there will be one show. And a show including some boy-girl duets where each boy-girl couple will sing with each other no more than one song and each participant will sing at least one song. Two show

A

and

B

are considered different if there is a boy-girl couple sing at show

A

but not show

B

. The contest will end if and only if every possible shows are performed, and each show is performed exactly one time.
a) A show is called depend on a participant

X

if we cancel all duets that

X

perform, then there will be at least one another participant will not sing any song in that show. Prove that among every shows that depend on

X

, the number of shows with odd number of songs equal to the number of shows with even number of songs.
b) Prove that the organizers can arrange the shows in order to make sure that the numbers of songs in two consecutive shows have different parity.

Problem Statement