HMMT 二月 2011 · TEAM2 赛 · 第 15 题
HMMT February 2011 — TEAM2 Round — Problem 15
题目详情
- [ 40 ] On Facebook, there is a group of people that satisfies the following two properties: (i) there exists a positive integers k such that any subset of 2 k − 1 people in the group contains a subset of k people in the group who are all friends with each other, and (ii) every member of the group has 2011 friends or fewer. (a) [ 15 ] If k = 2, determine, with proof, the maximum number of people the group may contain. (b) [ 25 ] If k = 776, determine, with proof, the maximum number of people the group may contain. Page 2 of 2
解析
- [ 40 ] On Facebook, there is a group of people that satisfies the following two properties: (i) there exists a positive integers k such that any subset of 2 k − 1 people in the group contains a subset of k people in the group who are all friends with each other, and (ii) every member of the group has 2011 friends or fewer. (a) [ 15 ] If k = 2, determine, with proof, the maximum number of people the group may contain. (b) [ 25 ] If k = 776, determine, with proof, the maximum number of people the group may contain. Solution: (a) Answer: 4024 If k = 2, then among any three people at least two of them are friends. Clearly if we have 4024 people divided into two sets of 2012 such that everyone is friends with everyone in their set but no one in the other set, then any triple of three people will contain two people from the same set, who will automatically be friends. Therefore, the group may contain 4024 people. We now prove that 4024 is the maximum. Given any set with at least 4025 people, consider any two people who are not friends. Between them them have at most 4022 friends, so by the pigeonhole principle there exists someone who is not friends with either one. Therefore, there exists a triple of three people who are all not friends with each other, so the group may not contain 4025 people or more, so 4024 is the maximum, as we claimed. (b) Answer: 4024 The answer remains the same. Considering the construction identical to that in the above solution, we see that the group may still contain 4024 people and satisfy the desired criterion. We now prove that 4024 is the maximum. Consider a group with at least 4025 people. From the previous part, we know there exist three people who are not friends. Pick such a threesome and call them X , Y , and Z . We now consider the rest of the people and successively pick pairs of persons A , B for 1 ≤ i ≤ 774 as follows: Once we have picked A , B , of the remaining 4019 − 2 i i i i i people, we find two who are not friends, which is always possible since 4019 − 2 i > 2013, and we name one of those people A and the other B . Once we have done this, consider the set i +1 i +1 containing X , Y , and Z as well as A and B for all 1 ≤ i ≤ 774. This is a set of 2 k − 1 = 1551 i i people. Any subset where everyone is friends with each other can contain at most 1 of A , B i i for all i , and at most 1 of X , Y , and Z , meaning that any such subset may contain at most 775 people. Hence there exists a subset containing 1551 people that does not have 776 people who are all friends. Thus, the group may not contain 4025 people or more, so the answer is still 4024, as desired. Team Round B