I got this problem from Rustan Leino, who got it from Pamela Zave.

I solved it and wrote up my solution.

Hilary and Jocelyn are throwing a dinner party at their house and have invited four other couples. After the guests arrive, people greet each other by shaking hands. As you would expect, a couple do not shake hands with each other and no two people shake each other's hands more than once. At some point during the handshaking process, Jocelyn gets up on a table and tells everyone to stop shaking hands. She also asks each person how many hands they've shaken and learns that no two people on the floor have shaken the same number of hands. How many hands has Hilary shaken?

She's shaken four hands, by the following reasoning.

The fewest hands anyone can shake is zero, and the most is eight. So, there are only nine different possible handshake counts. We're told there are nine people on the floor with distinct handshake counts, so among them they must have all the handshake counts ranging from zero to eight. Denote by $P_i$ the person on the floor with handshake count $i.$

$P_0$ hasn't shaken anyone's hand, so in particular she hasn't shaken hands with $P_8.$ But, $P_8$ has shaken eight people's hands, so she must have shaken everyone's hands but $P_0.$ $P_8$ didn't shake hands with her partner, and $P_0$ is the only one she hasn't shaken hands with, so $P_0$ and $P_8$ must be partners.

$P_1$ has only shaken one person's hand, and we know she's shaken $P_8$'s hand, so she hasn't shaken anyone else's hand. In particular, she hasn't shaken hands with $P_7.$ So, $P_7$ hasn't shaken hands with $P_0$ or $P_1.$ To have shaken hands with seven people, then, she must have shaken hands with everyone else besides those two. Now, $P_7$ hasn't shaken hands with her partner, so one of $P_0$ and $P_1$ must be her partner. But, we already know $P_0$'s partner is $P_8.$ So, $P_1$ and $P_7$ must be partners.

$P_2$ has only shaken two people's hands, and we know she's shaken $P_7$'s and $P_8$'s hands. So, she hasn't shaken anyone else's hand. In particular, she hasn't shaken $P_6$'s hand. So, $P_6$ hasn't shaken hands with $P_0,$ $P_1,$ or $P_2.$ To have shaken hands with six people, she must have shaken hands with everyone else besides those three. Now, $P_6$ hasn't shaken hands with her partner, so one of $P_0,$ $P_1,$ and $P_2$ must be her partner. We already know the partners for $P_0$ and $P_1$ and they aren't $P_6.$ So, $P_2$ and $P_6$ must be partners.

$P_3$ has only shaken three people's hands, and we know she's shaken $P_6$'s, $P_7$'s, and $P_8$'s hands. So, she hasn't shaken anyone else's hand. In particular, she hasn't shaken $P_5$'s hand. So, $P_5$ hasn't shaken hands with $P_0,$ $P_1,$ $P_2,$ or $P_3.$ To have shaken hands with five people, she must have shaken hands with everyone else besides those four. Now, $P_5$ hasn't shaken hands with her partner, so one of $P_0,$ $P_1,$ $P_2,$ and $P_3$ must be her partner. We already know the partners for $P_0,$ $P_1,$ and $P_2$ and they aren't $P_5.$ So, $P_3$ and $P_5$ must be partners.

We've paired up everyone besides Jocelyn and $P_4,$ so those two must be partners. We can conclude that Hilary is $P_4$ and thus we know she's shaken four hands.