## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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.
RightGuy Monday, October 26, 2009
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
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.
Diptesh chatterjee Sunday, November 29, 2009 |

Powered by FogBugz