Appariements de filles et garçons avec contraintes d'acquaintances

Il y a $n$ garçons et $n$ filles dans la ville A et chaque fille connaît tous les garçons. Il y a $n$ filles $g_1,g_2,\dots ,g_n$ et $2n-1$ garçons $b_1,b_2,\dots ,b_{2n-1}$ dans la ville B de sorte que la fille $g_i$ connaît uniquement les garçons $b_1,b_2,\dots ,b_{2i-1}$ (avec $i\in [[1,n]]$). Pour chaque $r\in [[1,n]]$, on choisit $r$ filles et $r$ garçons de la ville A, et de même pour la ville B, puis on les partage en $r$ couples pour danser (une fille et un garçon) de sorte que : le partenaire de la fille dans chaque paire est connu par elle. Soient $A_n(r)$ et $B_n(r)$ le nombre de façons pour choisir $r$ filles et $r$ garçons dans la ville A et la ville B respectivement.

Montrer que $A_n(r)=B_n(r)$. (Proposé à l'OIM, 1997)