An Even Number of Odd People
The puzzle
At a party, some people shake hands with some others. Prove that the number of people who shook hands an odd number of times is even.
No assumption about who shook whose hand - this holds for every possible party.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Count the total number of hands shaken, adding up each person's tally.
Hint 2
Each handshake involves two people, so it contributes 2 to that total.
Show the answer Hide the answer
The sum of everybody's handshake count is twice the number of handshakes, hence even — and a sum of whole numbers is even only if an even number of them are odd.
How to get there
Add up every person's handshake count. Each handshake is counted twice, once by each participant, so the total is exactly twice the number of handshakes. With 7 handshakes the total is 14, whatever the arrangement.
An even total cannot be made from an odd number of odd contributions: odd plus odd is even, and adding a third odd makes it odd again. So the count of odd-handshake people must be even.
This is the handshake lemma, and it is the reason the Konigsberg bridges cannot be walked: a graph always has an even number of odd-degree vertices, so four odd landmasses is a legitimate configuration but three would be impossible to draw at all.
The technique worth keeping
Count the same quantity two ways and set the results equal. Here each handshake is counted once as an event and twice as a participation, and that factor of two is the entire proof.