In town
![A,](/media/m/8/6/5/865743fba196abcc2b01372b2f0205c1.png)
there are
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
girls and
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
boys, and each girl knows each boy. In town
![B,](/media/m/1/6/e/16e519ccc501d3fbc4fe4ab09a16195c.png)
there are
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
girls
![g_1, g_2, \ldots, g_n](/media/m/1/5/a/15a9b9a589c0f11502a07ed419bdb28d.png)
and
![2n - 1](/media/m/d/f/8/df883cf64f335e260ddf6ffbf1141afc.png)
boys
![b_1, b_2, \ldots, b_{2n-1}.](/media/m/d/e/9/de99bdf13a49187dcab8dc555164856c.png)
The girl
![i = 1, 2, \ldots, n,](/media/m/e/0/6/e06597b8e994a192ea702cb7a8ef3f08.png)
knows the boys
![b_1, b_2, \ldots, b_{2i-1},](/media/m/c/3/0/c30fee0c9d2f13ddb07ce40bf3636074.png)
and no others. For all
![r = 1, 2, \ldots, n,](/media/m/5/1/e/51e0a42dbebb2c735baf4afe1ed2057b.png)
denote by
![A(r),B(r)](/media/m/6/8/d/68df1c6f747dff577a0ea84a1c3782e1.png)
the number of different ways in which
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
girls from town
![A,](/media/m/8/6/5/865743fba196abcc2b01372b2f0205c1.png)
respectively town
![B,](/media/m/1/6/e/16e519ccc501d3fbc4fe4ab09a16195c.png)
can dance with
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
boys from their own town, forming
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
pairs, each girl with a boy she knows. Prove that
![A(r) = B(r)](/media/m/8/9/a/89a3cf036a193b5b0eb87891a1af245d.png)
for each
%V0
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.$