Gate Computer Science group Fb post

Question

Comments

answer is C?

---

Don't know the answer :( .. What is your approach?

---

Let no of elements in each equivalence class be 'n'.

Now, asper handshaking theorem, there will be nP₂ elemnts in the relation R corresponding to single equivalence class. Similarly , nP₂ for the remaining 2 classes.

So, total elements = (nP₂)³

Here, in the options, only option (C) is proper cube. So, I think (C) is the answer.

---

Did not get the Handshaing Theorem in this context .. can u plz provide any link or resources on this part?

---

Handshaking means ordered pairs.

Sorry, it wont be nP₂. It would be n²

e.g if the equivalence class is {1,2,3} then the ordered pairs will be n² = 3² = 9

i.e R will contain ordered pairs

1,1

2,2

3,3

1,2

2,1

2,3

3,2

1,3

3,1

Right?

---

That's okay but did not get " total elements = (nP₂)^3 "

---

It should be (n²)³

---

why (n²)^{3 ?}

^{did not understand the cube part..}

---

There are 3 equivalence classes of same size. Thts why. Read the question carefully.

---

at least 3 equivalence class not exactly 3 is mentioned even if we consider 3 equivalence classes then total number of ordered pairs (according to your previous explanation) becomes 3*n^2 not (n²)³

---

Oops...I read the question wrong. But still consider

#total elements = k. n²        

Now, try to find the factors of any of the answers and check if we can get a perfect square. Since,

 k >= 3

we can take k=4 so that we get (D) as the answer.