HMMT November

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.