HMMT 十一月 2015 · 团队赛 · 第 6 题

英文解析

6. [ 5 ] Marcus and four of his relatives are at a party. Each pair of the five people are either friends orenemies . For any two enemies, there is no person that they are both friends with. In how many waysis this possible?
   Proposed by: Alexander Katz
   Answer: 52
   Denote friendship between two people a and b by a ∼ b . Then, assuming everyone is friends withthemselves, the following conditions are satisfied:
   • a ∼ a
   • If a ∼ b , then b ∼ a
   • If a ∼ b and b ∼ c , then a ∼ c
   Thus we can separate the five people into a few groups (possibly one group), such that people arefriends within each group, but two people are enemies when they are in different groups. Here comesthe calculation. Since the number of group(s) can be 1, 2, 3, 4, or 5, we calculate for each of thosecases. When there’s only one group, then we only have 1 possibility that we have a group of 5, and
   ( )
   the total number of friendship assignments in this case is = 1; when there are two groups, we 5
   ( ) ( )5
   5 5
   have 5 = 1 + 4 = 2 + 3 are all possible numbers of the two groups, with a total of + = 15
   1 2
   5 5
   ( )
   ( )( )
   1 25
   choices; when there are three groups, then we have 5 = 1 + 1 + 3 = 1 + 2 + 2, with + = 25
   3 2
   possibilities; when there are four of them, then we have 5 = 1 + 1 + 1 + 2 be its only possibility, with
   ( ) = 10 separations; when there are 5 groups, obviously we have 1 possibility. Hence, we have a total 5
   of 1 + 15 + 25 + 10 + 1 = 52 possibilities.2
   Alternatively, we can also solve the problem recursively. Let B be the number of friendship graphsn
   ( )
   with n people, and consider an arbitrary group. If this group has size k , then there are possible suchnkgroups, and B friendship graphs on the remaining n − k people. Therefore, we have the recursionn − k
   ( )
   ∑nn
   B = Bn n − kk =0 kwith the initial condition B = 1. Calculating routinely gives B = 52 as before.
   1 5