MathDB

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 \minus{} 1 boys b_1, b_2, \ldots, b_{2n\minus{}1}. The girl

g_i,

i \equal{} 1, 2, \ldots, n, knows the boys b_1, b_2, \ldots, b_{2i\minus{}1}, and no others. For all r \equal{} 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) \equal{} B(r) for each r \equal{} 1, 2, \ldots, n.

Problem Statement