AoPS - Problem

Source: IMO Shortlist 1997, Q13

Tags: combinatorics, counting, Combinatorial Identity, bijection, binomial coefficients, IMO Shortlist

orl

10.08.2008 06:17

In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n - 1$ boys $ b_1, b_2, \ldots, b_{2n-1}.$ The girl $ g_i,$ $ i = 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i-1},$ and no others. For all $ r = 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) = B(r)$ for each $ r = 1, 2, \ldots, n.$

Let $ A(n,r)$ and $ B(n,r)$ be the number of ways of possible dance pairs from town A and Town B out of total $ n$ girls respectively. Enumerating $ A(n,r)$ we get, \[ A(n,r)={n\choose r}^2 r!\] Let us construct a recurrence relation for $ B(n,r)$ for $ 2\le r \le n$, Case1: When $ g_n$ is dancing. Let the rest of the $ r-1$ girls be paired in $ B(n-1,r-1)$ ways.The $ g_n$th girl can then be paired with any of the remaining $ 2n-r$ boys. Case2: When $ g_n$ is not dancing. We simply have $ B(n-1,r)$. Therefore, \[ B(n,r)=(2n-r)B(n-1,r-1) + B(n-1,r)\quad \forall \quad 2 \le r \le n\] and $ B(n,1)=1+3+\dots+2n-1=n^2$. It may be observed that $ A(n,r)$ and $ B(n,r)$ satisfy the same recurrence relation with same initial values and hence the conclusion.