HMMT 十一月 2015 · 团队赛 · 第 6 题
HMMT November 2015 — Team Round — Problem 6
题目详情
- [ 5 ] Marcus and four of his relatives are at a party. Each pair of the five people are either friends or enemies . For any two enemies, there is no person that they are both friends with. In how many ways is this possible?
解析
- [ 5 ] Marcus and four of his relatives are at a party. Each pair of the five people are either friends or enemies . For any two enemies, there is no person that they are both friends with. In how many ways is this possible? Proposed by: Alexander Katz Answer: 52 Denote friendship between two people a and b by a ∼ b . Then, assuming everyone is friends with themselves, 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 are friends within each group, but two people are enemies when they are in different groups. Here comes the calculation. Since the number of group(s) can be 1, 2, 3, 4, or 5, we calculate for each of those cases. When there’s only one group, then we only have 1 possibility that we have a group of 5, and ( ) 5 the total number of friendship assignments in this case is = 1; when there are two groups, we 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 ( ) ( )( ) 5 1 2 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 ( ) 5 = 10 separations; when there are 5 groups, obviously we have 1 possibility. Hence, we have a total 2 of 1 + 15 + 25 + 10 + 1 = 52 possibilities. Alternatively, we can also solve the problem recursively. Let B be the number of friendship graphs n ( ) n with n people, and consider an arbitrary group. If this group has size k , then there are possible such k groups, and B friendship graphs on the remaining n − k people. Therefore, we have the recursion n − k ( ) n ∑ n B = B n n − k k k =0 with the initial condition B = 1. Calculating routinely gives B = 52 as before. 1 5