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

HMMT February 2014 — Team Round — Problem 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 j only if girl G is willing to marry boy B . Given that there is exactly one way to pair each girl with a i j distinct boy that she is willing to marry, what is the maximal possible number of suitable pairs?

解析

[ 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 j only if girl G is willing to marry boy B . Given that there is exactly one way to pair each girl with a i j distinct 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 n 2 that there is an edge between vertices G and B if and only if ( G , B ) is suitable, so we want to i j i j maximize 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 G i 2 and B for all pairs j ≤ i , because the only possible matching in this case is pairing G with B for all j i i i . To prove that this is maximal, we first assume without loss of generality that our unique matching consists of pairing G with B for all i , which takes n edges. Now, note that for any i, j , at most one i i of the two edges G B and G B can be added, because if both were added, we could pair G with B i j j i i j ( ) n ( n − 1) n and G with B instead to get another valid matching. Therefore, we may add at most · 1 = j i 2 2 n ( n − 1) n ( n +1) edges, so the maximal number of edges is n + = as desired. 2 2