MathDB

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

Problem Statement