MathDB
2014 Team #3: Kinda Sorta the Marriage Lemma?

Source:

March 2, 2014

Problem Statement

There are nn girls G1,…,GnG_1,\ldots, G_n and nn boys B1,…,BnB_1,\ldots,B_n. A pair (Gi,Bj)(G_i,B_j) is called <spanclass=′latex−italic′>suitable</span><span class='latex-italic'>suitable</span> if and only if girl GiG_i is willing to marry boy BjB_j. Given that there is exactly one way to pair each girl with a distinct boy that she is willing to marry, what is the maximal possible number of suitable pairs?
Back to ProblemsView on AoPS