Q3 Matemática  (Benelux 2009)

Seja $n\ge 1$ um inteiro. Na cidade $X$ existem $n$ meninas e $n$ meninos, e cada menina conhece cada menino. Na cidade $Y$ existem $n$ meninas, $g_1,g_2,\dots ,g_n$, e $2n-1$ meninos, $b_1,b_2,\dots ,b_{2n-1}$. Para $i=1,2,\dots ,n$, a menina $g_i$ conhece os meninos $b_1,b_2,\dots ,b_{2i-1}$ e nenhum outro menino. Seja $r$ um inteiro com $1\le r\le n$. Em cada uma das cidades será realizada uma festa onde $r$ meninas daquela cidade e $r$ meninos da mesma cidade devem dançar uns com os outros em pares de $r$ dançantes. No entanto, toda garota só quer dançar com um garoto que conhece. Denote por $X(r)$ o número de maneiras pelas quais podemos escolher $r$ pares dançantes da cidade $X$, e por $Y(r)$ o número de maneiras pelas quais podemos escolher $r$ pares dançantes da cidade $Y$. Prove que $X(r)=Y(r)$ para $r=1,2,\dots ,n$.