HMMT-Nov 2023 thm, 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.

Solution: 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 there can only be at maximum $\left\lfloor\frac{15}{2}\right\rfloor=7$ pairs of people with reputation 1 . 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, there are at most 3 people left, so we have formed at least $\frac{17-3}{2}=7$ pairs. $\fbox{7}$.

Answer: 7