TIFR CSE 2019 | Part A | Question: 11

Question

Suppose there are $n$ guests at a party (and no hosts). As the night progresses, the guests meet each other and shake hands. The same pair of guests might shake hands multiple times. for some parties stretch late into the night , and it is hard to keep track.Still, they don’t shake hands with themselves. Let Odd be the set of guests who have shaken an odd number of hands, and let even be the set of guests who have shaken an even number of hands. Which of the following stays invariant throughout the night?

• A. $ \mid \text{Odd} \mid \text{ mod } 2$
• B. $\mid \text{Even} \mid $
• C. $\mid \text{Even} \mid – \mid \text{Odd} \mid$
• D. $2 \mid \text{Even} \mid – \mid \text{Odd} \mid$
• E. $2 \mid \text{Odd} \mid – \mid \text{Even} \mid$

Comments

Answer will be B)

taking example we have to answer

---

According to Handshaking Lemma, number of person with odd number of handshake is always even.

hence |odd| mod 2 is always 0.

answer: A

please point out if any mistake is there.

---

$\binom{n}{2}=even$

Now n can odd or even , ans always even

---

how do u know odd number of handshaked every time?

I donot think So,

Handshaking will be even or odd anything

but always total handshakes comes even

---

@srestha What do you mean by "answer"?

---

means total number of handshake throughout night will be always even

See

Say one of two group has like this

One group has 3 people , and another group has 2 people

So, 3 people each has 2 handshake , total 6 handshake........................i

And in other group has 2 people and each has 3 handshake, So, here also 6 handshake...................ii

Now, sum i and ii total 12 handshake

Like that take any example

Always get even handshake

right?

---

@srestha

how do u know odd number of handshaked every time?
 

this is what handshaking lemma says---- don't know how many odd handshakes exactly, but whatever it is, it will always be even.

means total number of handshake throughout night will be always even

it is true. total number of handshakes will be even. but exactly how many even handshakes?? we don't know. and option B is saying |even|, i.e; magnitude of number of even handshakes. how could we know that? 

---

Why do we put handshaking lemma, without simple logic?

---

ok , @aambazinga

take any two group of people , and tell me where u got it false

---

@srestha What you are telling is correct. But thats not what is asked in the question. 

---

Sir

mod2 will not be ans

mod2 just check a number is odd or not

---

@srestha

please check my answer.

Answer 1

According to Handshaking Lemma, number of person with odd number of handshake is always even.

Hence |odd| mod $2$ is always $0.$

Answer: A

Answer 2

Method 1.

Suppose there are $5$ guest in the party $G_1$, $G_2$, $G_3$, $G_4$ and $G_5$.

Question asks which of the options is constant irrespective of how many handshakes happened.

Let us take $2$ instances so that we can verify which of the following options is not changing.

Suppose party has just started and $G_5$ shake hands with everyone and $G_2, G_3$ shake hands $2$ times as shown.

 

Now after sometimes more handshakes happened and handshakes are as shown below

Note that here $G_1$ shake hands with $G_5$ $3$ times and $G_2,G_3$ shake hands $2$ times with each other respectively.

		$instance_1$	$instance_2$
$A.$	$|Odd|\ mod\ 2$	$4\ mod\ 2 = 0$ $(G_1, G_2,G_3,G_4)$	$2\ mod\ 2 = 0$ $(G_4,G_2)$
$B.$	$|Even|$	$1\ (G_5)$	$3 \ (G_1,G_3,G_5)$
$C.$	$|Even| - |Odd|$	$4-1 = 3$	$2 -3 = -1$
$D.$	$2|Even| - |Odd|$	$2 - 4 = -2$	$6 - 2 =4$
$E.$	$2|Odd| - |Even|$	$8 - 1 =7$	$4 - 3 =1$

 

Hence from the above table it is clear that Option $A.$ is the correct choice.

---

Method 2.

 

If you look at question carefully , then we can convert the question into question of Graph theory, which says if there can be multiple edges between vertices and no vertex can have self loops then which of the following options is correct.

Also we know from Handshaking theorem that Number of vertices with Odd degree in a graph is always Even.

So we can directly select Option $A.$ as correct choice.

Comments

@Satbir Can u tell me, what is wrong with option B?

Why r u telling odd number of member everytime?(like 5 member as u taken)

---

@srestha

Here $5$ i have choosen randomnly, you can take any number in place of $5$.(i.e. $n$ can be any number)

Option $B.$ is wrong as i shown in the example above.

option $B.$ is changing by taking different instances , hence it is not invariant.

Answer 3

Whenever a handshake happens,one of the following 3 cases may happen.

1--2 persons get added into Odd set

2--one person of Odd set get substituted by a new person.

3--2 persons get removed from the group.

EXAMPLE:

Consider there are 4 persons a,b,c,d in party.

Let us see what happens for every hand shake.

1--a,b shake hands. Now Odd={a,b} ,even={}

2--c,d shake hands.Now Odd={a,b,c,d},even={}.

3--a,b shake hands again.Now Odd={c,d},even={a,b}.Since a,b had 2 handshakes each and c,d had 1 hand shake each.

4--a,c shake hands.Now Odd={a,d},even={c,b}.since a had 3 hand shakes,d had 1 hand shake ,c and b had 2 handshakes each.

Therefore we can say that after every hand shake, cardinality of Odd set will either increase by 2 or remains same or decrease by 2. So cardinality of Odd set is always even .

Hence option A is true.

you can see other options value may change for a new handshake.

Ps:

If 2 persons in Odd set shake hand ,then both of them move into Even set.

If 2 persons in Even set shake hand,then both of them move into Odd set.

If a person x in Odd set and person y in even set shake hand,then x moves into Odd set and y moves into Even set.

 

Answer 4

Answer : A

This is Fundamental Problem of GRAPH THEORY

From the concept of GRAPH THEORY :  In Any Graph there are an EVEN no. of Odd Degree Vertices .

So, for N Guests , no. of guests shake Hand with other guests ODD no. of times is Always Even . 

so, |Odd | mod 2 

 |Odd| , no. of Odd hand shaking is always Even

so,  |Odd | mod 2  = 0