techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Prove this fact

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
 
 
Double count the number of handshakes mod 2. Check your favorite combinatorics book for more details.
d Send private email
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
Trying This Send private email
Tuesday, October 27, 2009
 
 
Thank god for small parties.
Viladge Idi@
Tuesday, October 27, 2009
 
 
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.
Sameer Deshpande Send private email
Wednesday, October 28, 2009
 
 
Nice pointer Sameer!!
Imran Shaikh Send private email
Wednesday, November 18, 2009
 
 
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.
evan Send private email
Wednesday, November 18, 2009
 
 
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
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz