HMMT 二月 2014 · 团队赛 · 第 3 题

英文解析

3. [ 15 ] There are n girls G , . . . , G and n boys B , . . . , B . A pair ( G , B ) is called suitable if and
   1 n 1 n i jonly if girl G is willing to marry boy B . Given that there is exactly one way to pair each girl with ai jdistinct boy that she is willing to marry, what is the maximal possible number of suitable pairs?
   n ( n +1)
   Answer: We represent the problem as a graph with vertices G , . . . , G , B , . . . , B such
   1 n 1 nthat there is an edge between vertices G and B if and only if ( G , B ) is suitable, so we want to 2
   i j i jmaximize the number of edges while having a unique matching.
   n ( n +1)
   We claim the answer is . First, note that this can be achieved by having an edge between Giand B for all pairs j ≤ i , because the only possible matching in this case is pairing G with B for all 2
   j i ii . To prove that this is maximal, we first assume without loss of generality that our unique matchingconsists of pairing G with B for all i , which takes n edges. Now, note that for any i, j , at most onei iof the two edges G B and G B can be added, because if both were added, we could pair G with Bi j j i i j
   ( )
   n ( n − 1)
   and G with B instead to get another valid matching. Therefore, we may add at most · 1 =nj i
   2 2
   n ( n − 1) n ( n +1)
   edges, so the maximal number of edges is n + = as desired.
   2 2