# Handshake problem. discrete math.

at a party, 25 guests mingle and shake hands. prove that at least one guest must have shaken hands with an even number of guests.

-
Might help: The Handshaking theorem: en.wikipedia.org/wiki/Handshaking_lemma –  Sujaan Kunalan Jun 20 '13 at 3:49

HINT: Number the guests $1$ through $25$. Let $a_k$ be the number of guests with whom guest $k$ shook hands. Suppose that the numbers $a_1,a_2,\dots,a_{25}$ are all odd.
• Is $\sum_{k=1}^{25}a_k$ odd, or is it even?
• Each handshake involves two people, so each handshake is counted twice in $\sum_{k=1}^{25}a_k$, once for each of the two people involved. What does this imply about whether $\sum_{k=1}^{25}a_k$ is odd or even?