I´d like to know if I understand correctly the argument behind the even-odd handshake problem. Basically the theorem says that the number of persons who have shaken an odd number of hands is even.
My reasoning goes like this. Suppose that the number of people who have shaken an odd number of hands is odd. Then the expression for number of handshakes in that group is : 2a+1 + 2b+1 + 2c+1 + … 2z+1 which has an odd number of terms. So we have an odd number of odd numbers and that gets us that the number of handshakes in the group is an odd number. But! We also know that a number of handshakes in any group has to be even (since every handshake gets counted twice.) Contradiction.
Btw I didn´t come up with the proof, I am just trying to understand a proof which I found on-line. Is my understanding sound?
Best Answer
The total number of handshakes overall has to be even.
Suppose the number of people who have shaken an odd number of hands is odd. Odd times odd is odd. So the total handshakes in this group is odd.
The number of people who have shaken an even number of hands can odd or even. But the total hands shaken by them will always be even times even or even times odd = even.
Adding them up gives a contradiction that says "odd + even = even".
Edit: You need to consider the sum of hands shaken in both groups instead of just the "odd handshake group" because the "odd group" could have shaken hands with people outside of their group too and so is allowed to have shaken an odd number of hands.
i.e. It is not true that the total number of hands shaken by a subset of the group has to be even.