VMO

a. Label all the girls by $1,2,\dots ,m$ and boys by $1,2,\dots ,n$. For each show, we display the performances of this show by a $m\times n$ table in which the number lies on the intersection of $i$th row and $j$th column is $1$ if $i$th girl performed with $j$th boy in this show. $0$ otherwise.

Call a table "nice" if the sum of all elements on each row and column is positive. It is obvious that all the tables that related to each show has to be nice.

For a student $X$, without loss of generality, we assume that $X$ is a girl. By the assumption, a show which is depended on $X$ if on its table, there exists a column that has only one cell that is marked by $1$ on $X$th row. Assume that there are $k$ columns which are depended on $X$ hence $k<n$ because otherwise, there must exist a row that contain all cell marked by $0$. The other $n-k$ cells on $X$th row could be marked by either $0$ or $1$ because on their columns, thus there exists another cell that is marked by $1$.

Hence the number of tables depending on $X$ in this case is $2^{n-k}$ times the number of "nice" tables that consists of $m-1$ other rows and $n-k$ other columns, after removing the row of student $X$ and all its depended column. However, on each of these tables, if we relabel $(1\to 0,0\to 1)$ a number on the cell that on $X$th row but is not depend on $X$, we will obtain a new table which is linked to the show and has different parity when compared to the number of songs that sung by $X$ from the initial show. It deduces that the number of shows that depends on $X$ where $X$ performs even number of songs is half of the number of shows that depends on $X$.

b. A table is called "odd" if there are odd number of cells marked by $1$ on this table. Otherwise, the table is called "even". Let $f(m,n)$ and $g(m,n)$ be the number of "nice" tables that has odd and even numbers of $1$ respectively. Let $X$ be an arbitrary girl.

If there exists a column that depends on $X$, then the number of even tables is equal to that of odd tables. Denoted this value by $h(m,n)$. Otherwise, removing $X$th row and we obtain a $(m-1)\times n$ 'nice' table.

On the other hand, the number of tables that $X$th row is marked with odd and even number of $1$ is respectively equal to $$L=\sum _{2|a-1}\left(\genfrac{}{}{0ex}{}{n}{a}\right)\text{and}C=\sum _{2|a,a>0}\left(\genfrac{}{}{0ex}{}{n}{a}\right).$$ It is well-known that $(x+1{)}^n=(\genfrac{}{}{0ex}{}{n}{0})+x(\genfrac{}{}{0ex}{}{n}{1})+\cdots +x^n(\genfrac{}{}{0ex}{}{n}{n})$ and by letting $x=-1$, we get $L=C+1$. Note that the parity of $X$th row determines the parity of the table, hence we have the formula $$\{\begin{array}{l}f(m,n)=h(m,n)+L\cdot g(m-1,n)+C\cdot f(m-1,n),\\ g(m,n)=h(m,n)+L\cdot f(m-1,n)+C\cdot g(m-1,n).\end{array}$$ Thus, $$\begin{array}{rl}f(m,n)-g(m,n)& =(L-C)(g(m-1,n)-f(m-1,n))\\ & =g(m-1,n)-f(m-1,n).\end{array}$$ By induction, we have $$f(m,n)-g(m,n)=(-1{)}^{m+n-4}(f(2,2)-g(2,2)).$$ It is obvious that $f(2,2)=3$ and $g(2,2)=4$ hence $$f(m,n)-g(m,n)=(-1{)}^{m+n-3}.$$ Since the difference between odd and even tables is $1$, it is able to arrange the shows such that the number of songs in two consecutive shows has different parity.

​