HMMT 十一月 2023 · THM 赛 · 第 3 题

HMMT November 2023 — THM Round — Problem 3

There are 17 people at a party, and each has a reputation that is either 1 , 2 , 3 , 4 , or 5 . Some of them split into pairs under the condition that within each pair, the two people’s reputations differ by at most 1 . Compute the largest value of k such that no matter what the reputations of these people are, they are able to form k pairs.

解析

There are 17 people at a party, and each has a reputation that is either 1, 2, 3, 4, or 5. Some of them split into pairs under the condition that within each pair, the two people’s reputations differ by at most 1. Compute the largest value of k such that no matter what the reputations of these people are, they are able to form k pairs. Proposed by: Albert Wang Answer: 7 Solution: First, note that k = 8 fails when there are 15, 0, 1, 0, 1 people of reputation 1, 2, 3, 4, 5, respectively. This is because the two people with reputation 3 and 5 cannot pair with anyone, and 15 there can only be at maximum ⌊ ⌋ = 7 pairs of people with reputation 1. 2 Now, we show that k = 7 works. Suppose that we keep pairing people until we cannot make a pair anymore. Consider that moment. If there are two people with the same reputation, then these two people can pair up. Thus, there is at most one person for each reputation. Furthermore, if there are at least 4 people, then there must exist two people of consecutive reputations, so they can pair up. Thus, 17 − 3 there are at most 3 people left, so we have formed at least = 7 pairs. 2