IMO 1997 SL 13

Origin: IND

Problem

In town A, there are n girls and n boys, and each girl knows each boy. In town B, there are n girls g1, g2, . . . , gn and 2n −1 boys b1, b2, . . ., b2n−1. The girl gi, i = 1, 2, . . ., n, knows the boys b1, b2, . . . , b2i−1, and no others. For all r = 1, 2, . . ., 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, . . . , n.

Solution

Denote A(r) and B(r) by A(n, r) and B(n, r) respectively. The numbers A(n, r) can be found directly: one can choose r girls and r boys in
n r 2 ways, and pair them in r! ways. Hence A(n, r) = n r 2 \cdot r! = n!2 (n −r)!2r!. Now we establish a recurrence relation between the B(n, r)’s. Let n \geq2 and 2 \leqr \leqn. There are two cases for a desired selection of r pairs of girls and boys: (i) One of the girls dancing is gn. Then the other r −1 girls can choose their partners in B(n −1, r −1) ways and gn can choose any of the remaining 2n −r boys. Thus, the total number of choices in this case is (2n −r)B(n −1, r −1). (ii) gn is not dancing. Then there are exactly B(n −1, r) possible choices. Therefore, for every n \geq2 it holds that B(n, r) = (2n −r)B(n −1, r −1) + B(n −1, r) for r = 2, . . . , n. Here we assume that B(n, r) = 0 for r > n, while B(n, 1) = 1 + 3 + \cdot \cdot \cdot + (2n −1) = n2. It is directly verified that the numbers A(n, r) satisfy the same initial conditions and recurrence relations, from which it follows that A(n, r) = B(n, r) for all n and r \leqn.