5 married couples gather at a party. As they come in and greet each other, various people exchange handshakes - but, of course, people never shake hands with themselves or with their own respective spouses. At the end of the party, one woman goes around asking people how many hands they shook, and she gets nine different answers. How many hands did she herself shake?
Suppose that there were $n$ couples, and the woman asked all $2 n-1$ other attendees how many hands they shook and received $2 n-1$ different answers. We will show that she herself shook $n-1$ hands; hence, in our particular case, the answer is 4 .

We work by induction. When $n=1$, there is one couple, and no handshakes can occur, proving the base case. Now suppose the result holds for $n$ couples; we will prove it is valid for $n+1$ couples. With $n+1$ couples present, the woman receives $2 n+1$ different answers to her question. But no person $P$ can shake more than $2 n$ hands (for $2 n+2$ people, minus $P$ and $P$ 's spouse); hence, these $2 n+1$ numbers must be exactly $0,1,2, \ldots, 2 n$ in some order. In particular, one of these people, $A$, shook everyone else's hand except $A$ 's own spouse (that accounts for the " $2 n$ " answer), and another, $B$, shook no hands (the " 0 " answer). Because $B$ did not shake $A$ 's hand, $A$ and $B$ must be married to each other. The remaining $2 n$ people include the woman who asked the question, together with those who answered $1,2, \ldots, 2 n-1$ to her question. Now pretend that $A$ and $B$ had not attended the party, so we are left with $n$ couples. Each of these people shook hands with $A$ and not with $B$; therefore, when $A$ and $B$ are removed, their handshake counts become $0,1,2, \ldots, 2 n-2$. Hence, by the induction hypothesis, the questioner shook $n-1$ hands. But now, if we put $A$ and $B$ back in, we note that the woman shook $A$ 's hand as well (and not $B$ 's). So, altogether, she shook $n$ hands. This completes the induction step, and now the proof is done.