HMMT 二月 2011 · TEAM2 赛 · 第 15 题

英文解析

15. [ 40 ] On Facebook, there is a group of people that satisfies the following two properties: (i) there existsa positive integers k such that any subset of 2 k − 1 people in the group contains a subset of k peoplein the group who are all friends with each other, and (ii) every member of the group has 2011 friendsor 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. Clearlyif we have 4024 people divided into two sets of 2012 such that everyone is friends with everyone intheir 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, considerany two people who are not friends. Between them them have at most 4022 friends, so by thepigeonhole principle there exists someone who is not friends with either one. Therefore, thereexists a triple of three people who are all not friends with each other, so the group may notcontain 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 thatin the above solution, we see that the group may still contain 4024 people and satisfy the desiredcriterion.
    We now prove that 4024 is the maximum. Consider a group with at least 4025 people. Fromthe previous part, we know there exist three people who are not friends. Pick such a threesomeand call them X , Y , and Z . We now consider the rest of the people and successively pick pairs ofpersons A , B for 1 ≤ i ≤ 774 as follows: Once we have picked A , B , of the remaining 4019 − 2 ii i i ipeople, we find two who are not friends, which is always possible since 4019 − 2 i > 2013, andwe name one of those people A and the other B . Once we have done this, consider the seti +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 ipeople. Any subset where everyone is friends with each other can contain at most 1 of A , Bi ifor 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 whoare all friends. Thus, the group may not contain 4025 people or more, so the answer is still 4024,
    as desired.
    Team Round B