BxMO 2009 Problem 3

Let $n\ge 1$ be an integer. In town $X$ there are $n$ girls and $n$ boys, and each girl knows each boy. In town $Y$ there are $n$ girls, $g_1,g_2,\ldots ,g_n$ , and $2n-1$ boys, $b_1,b_2,\ldots ,b_{2n-1}$ . For $i=1,2,\ldots ,n$ , girl $g_i$ knows boys $b_1,b_2,\ldots ,b_{2i-1}$ and no other boys. Let $r$ be an integer with $1\le r\le n$ . In each of the towns a party will be held where $r$ girls from that town and $r$ boys from the same town are supposed to dance with each other in $r$ dancing pairs. However, every girl only wants to dance with a boy she knows. Denote by $X(r)$ the number of ways in which we can choose $r$ dancing pairs from town $X$ , and by $Y(r)$ the number of ways in which we can choose $r$ dancing pairs from town $Y$ . Prove that $X(r)=Y(r)$ for $r=1,2,\ldots ,n$ .