Q14 Matemática  (IMO Shortlist 1997)

Na cidade $A,$ há $n$ meninas e $n$ meninos, e cada menina conhece cada menino. Na cidade $B,$ existem $n$ meninas $g_1,g_2,\dots ,g_n$ e $2n-1$ meninos $b_1,b_2,\dots ,b_{2n-1}.$ A menina $g_i,$ $i=1,2,\dots ,n,$ conhece os meninos $b_1,b_2,\dots ,b_{2i-1},$ e nenhum outro. Para todo $r=1,2,\dots ,n,$ denota por $A(r),B(r)$ o número de maneiras diferentes pelas quais $r$ meninas da cidade $A,$ respectivamente da cidade $B,$ pode dançar com $r$ meninos de sua própria cidade, formando duplas $r$, cada menina com um menino que ela conhece. Prove que $A(r)=B(r)$ para cada $r=1,2,\dots ,n.$