Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.
My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.
For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:
- Case 1: The new person's parity is even
- Case 2: The new person's parity is odd
But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.
Best Answer
Equivalently, parities have an even sum. The base step $n=0$ is trivial. Assume $n=k$ works, then add person $k+1$. If they shake hands with $j$ of the first $k$ people, the sum of parities increases modulo $2$ by $j+j=2j=0$.