GATE Overflow | Mathematics | Test 1 | Question: 15

Question

At any time total number of persons on earth who have shaken hands an odd number of times has to be

• A. an even number 
• B. an odd number
• C. a prime number 
• D. a perfect square

Comments

ok

if that is ur answer

take 7 person

then total number of hand shake = $_{2}^{7}\textrm{C}=21$

Now, odd number of people shaking hands odd number of times.

Now what u tell?

---

Now it's zero number of person shaking hands with odd number no of person, because all 7 are shaking hands with 6 other person(even no of person).

---

No, number of shaking hand is still odd

Answer 1

Lets consider a graph where each node represent a person and an edge denotes that two person have done handshake. So, our problem reduces to finding the number of nodes in a graph with odd degree and to see if this is even.

Each edge in a graph contribute 2 to the sum of degrees. i.e.,

Sum of degrees in a graph $ = 2e.$

For any vertex in the graph, its degree is either odd or even. So,

Sum of degrees in a graph = Sum of degrees of odd degree vertices + Sum of degrees of even degree vertices

So,

Sum of degrees of odd degree vertices = Sum of degrees in a graph - Sum of degrees of even degree vertices

Here, both terms on RHS are multiple of 2, as first one is $2e$ and sum of even numbers is always even. The difference of two even numbers is also even, and hence sum of degrees of odd degree vertices in a graph is even. We get an even number when we add odd numbers "even" number of times and not otherwise. So, number of vertices with odd degree in any graph must be even. 

Answer 2

answer will be even

first thing in order to shake hands odd no. of time we must haven even no. of person

let we have n persons then each will do handshaking with (n-1) persons.

it does not mean that if 1st person will do (n-1) then 2nd will do (n-2) etc(there is no restriction mentioned in question)

so for each person we have n-1 choices and to make n-1 as odd, we must have n as even