RSS Feed

techInterview Discussion

A marriage party is going on and handshakes are going on.
A person is an odd person if he has exchanged an odd number of handshakes. Prove that at any moment there is an even number of odd
persons.

Double count the number of handshakes mod 2. Check your favorite combinatorics book for more details.

Number of people required for ONE handshake = 2
Let Number of handshake = n
Assuming 2 people will only handshake once.

Let the total number of people in party = P
---------------------------------------------------

If P=2 (A,B)
n=0,
People with odd number of handshakes> 0
People with even number of handshakes> 0

AB  - n=1,
People with odd number of handshakes> 2
People with even number of handshakes> 0



----------------------------------------------------

If P=3 (A,B,C)
n=0,
People with odd number of handshakes> 0
People with even number of handshakes> 0

AB - n=1,
People with odd number of handshakes> 2
People with even number of handshakes> 0

BC - n=2,
People with odd number of handshakes> 2
People with even number of handshakes> 1

AC - n=3,
People with odd number of handshakes> 0
People with even number of handshakes> 3

----------------------------------------------------

If P=4(A,B,C,D)
n=0,
People with odd number of handshakes> 0
People with even number of handshakes> 0

AB - n=1,
People with odd number of handshakes> 2
People with even number of handshakes> 0

AC - n=2,
People with odd number of handshakes> 2
People with even number of handshakes> 1

BC - n=3,
People with odd number of handshakes> 0
People with even number of handshakes> 3

AD - n=4,
People with odd number of handshakes> 2
People with even number of handshakes> 2

BD - n=5,
People with odd number of handshakes> 2
People with even number of handshakes> 2

CD - n=6,
People with odd number of handshakes> 4
People with even number of handshakes> 0

Thank god for small parties.

Consider the possibilties,

Even meets Odd -> Change in odd count = 0
Even meets Even -> Change in odd count = +2
Odd meets Odd -> Change in odd count = -2

Every handshake changes the number of odds by either +2 or -2, so the final sum has to be even.

Nice pointer Sameer!!

Assume that Mr. Tim and Mr. Tom are handshaking, Mr. Tim's handshake number adds one, so is Mr. Tom's. So it said that each handshaking contribute two to the total handshaking number. And the total number  of handshaking should be even, at any moment.

Now let us see the problem.
Suppose that the number of odd persons is odd, then the total number of handshaking wont be even any more. So the number of odd persons must be even.

This can be efficiently proved using graph theory. Suppose we build a graph as follows:

V={Set of all the people}
E={(vi,vj)| vi shakes hands with vj}

Then the number of handshakes boils down to the degree of a vertex in the graph. And its known that the number of odd degree nodes in a rgaph has to be even. So there will always be an even number of odd persons.