GATE CSE 2015 Set 1 | Question: 34

Question

Suppose $L = \left\{ p, q, r, s, t\right\}$ is a lattice represented by the following Hasse diagram:

For any $x, y \in L$, not necessarily distinct , $x \vee y$ and $x \wedge y$ are join and meet of $x, y$, respectively. Let $L^3 = \left\{\left(x, y, z\right): x, y, z \in L\right\}$ be the set of all ordered triplets of the elements of $L$. Let $p_{r}$ be the probability that an element $\left(x, y,z\right) \in L^3$ chosen equiprobably satisfies $x \vee (y \wedge z) = (x \vee  y) \wedge (x \vee  z)$. Then

• A. $p_r = 0$
• B. $p_r = 1$
• C. $0 < p_r ≤ \frac{1}{5}$
• D. $\frac{1}{5} < p_r < 1$

Comments

@Kabir5454 Yes it was a typo. Sorry.. I have corrected it.

---

if the same question is asked for pentagon structure what would be the probability?

---

good expanation 

https://gateoverflow.in/8281/gate-cse-2015-set-1-question-34?show=107088#a107088

Answer 1

Number of elements in $L^3 =$ Number of ways in which we can choose $3$ elements from $5$ with repetition $= 5 * 5 * 5 = 125.$

Now, when we take $x = t,$ then the given condition for $L$ is satisfied for any $y$ and $z.$ Here, $y$ and $z$ can be taken in $5 * 5 = 25$ ways. 

Take $x = r, y = p, z = p.$ Here also, the given condition is satisfied.
When $x = t,$ we have $5*5 = 25$ cases $($for any $y$ and $z$$)$ where the given conditions are satisfied. Now, with $x = r, y = p, z = p,$ we have one more case. So, $26/125$ which means strictly greater than $1/5.$
So, this makes $p_r > \frac{25}{125}$ 

Also,
for $x = q, y = r, z = s,$ the given condition is not satisfied as $q \vee (r \wedge s) = q \vee p = q,$ while $(q \vee r) \wedge  (q \vee s) = t \wedge t = t.$ So, $p_r \neq 1.$

These findings make option A, B, C as FALSE.

Hence, answer = option D

Comments

I think P2>P1 is correct. See this link

https://csedoubts.gateoverflow.in/23909/%23self_doubt-%23set-theory-%23gatecse2015

 

---

when x=t how are you sure that for all y and z the given condition will be satisfied

---

@Shreyash007

Assuming $x=t$ , consider $x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$ 

For L.H.S, since $\vee$ denotes LUB ( Least Upper bound ) and $LUB(x,y)$ = $x$ , $\forall y$ as $x$ is the maximal element

For futher details, refer https://en.wikipedia.org/wiki/Join_and_meet

Similarly, for R.H.S, applying same principle, for any $r,s$

$(x \vee r) \wedge (x \vee s) = x \wedge x = x$

So, if $x = t$ then $y,z$ can take any of the 5 possible values with repetition giving 25 possibilities

Answer 2

Each element of {q,r,s} has two complement.So,these element can't be chosen in the triplets<x,y,z>.One element should be such that it has unique complement to meet the given distributive property.

So,ways can't be chosen = 3! = 6

(q,r,s)(q,s,r)(r,s,q)(r,q,s)(s,q,r)(s,r,q)

So,<x,y,z> be chosen 5$\times$5$\times$5=125 ways.

So,Ans = $\frac{125-6}{125}$ = $\frac{1}{5}\lt\frac{119}{125}\lt1$       (D)

Comments

Distributive Lattice property here. When CL is distributive, complement is always unique. (y)

---

If we take a triplet <t,r,p>

where r has 2 complement. So, according to this logic it shouldnot satisfy distributive property

But how it is satisfying?

---

What he is saying is if at least one of those 3 is having unique complement then it will satisfy the distributive property.

Here in your eg., t and p both have a single complement so a/c to his definition it should be correct.

---

Please share a reference for your answer's theory

---

@adactive18 @sreshta

Fine,r has two complement,but if atleast one of <x,y,z> has unique complement it will satisfy the given property.You can check by yourself or please provide a counter example for my solution.Thanks.

---

what about triples containing <q,r,t> here q, r, t don't have unique complements. you haven't  considered this kind of triplets

---

aditi19 <q,r,t> satisfies distributive property right?

---

@aditi19 t has unique complement so it will satisfy distributive property.

---

@rajashish I'm not sure but, if we take all the elements as same. for e.g <q, q, q>, here no element has a unique complement, but still, the left and right-hand side of equations come out to be q?

We can take all elements as same because we're considering the total no of cases as 5*5*5.

---

Wali counter example would be when we choose a triplet <r,r,r> (note: the elements in a triplet may not be distinct so we can take this) now in this triplet no element has a unique compliment but it still holds the distributive property ( r meet r = r, r join r = r)
I think when we choose a triplet such that no element has more than one of its compliments in the triplet itself then it is distributive.

---

thanks for this easy explanation

Answer 3

For p_r =1 we have to satisfy the condition of distributive lattice i.e. x V (y ⋀ z) = (x V y ) ⋀ (x V z) 

but it is not distributive as q has here more than one complement.

If we take (q,r,s) and apply distributive formula, we can see it is not satisfying i.e.  x V (y ⋀ z) ≠ (x V y ) ⋀ (x V z) 

So, from here we can say obviously p_r < 1

Here(x,y,z) can take p,q,r,s,t i.e. 5 values in 5*5*5=125 ways

Now, for proving  p_r >1/5 we have to check some triplets which satisfying distributive conditions, 

take for t 

(t,t,t),(t,t,q),(t,t,r),(t,t,s),(t,t,p),

(t,q,t),(t,q,q),(t,q,r),(t,q,s),(t,q,p),

(t,r,t)................................(t,r,p),

(t,s,t)................................(t,s,p),

(t,p,t).................................(t,p,p)

these 25 points satisfied distributive property, right?i.e. p_r =25/125=1/5

Now take 1 more point to say p_r>1/5

take any  satisfactory point .e.g  take (r,r,p) 

So, we can easily say 1/5 < p_r < 1

Ans (D)

Comments

yes..

---

Another easy view of this question is

it is not distributive lattice as there are more than one complement for point q,r,s

But individually some point must be distributive

So, option A) and B) ruled out easily

Now question lies, which points are not distributive?

For any combination of q,r,s will not be distributive

So, there will be 3!=6 combination will be not distributive

Among 125 combinations 6 are not distributive and 119 distributive

So, ans will be easily D)

---

So can we conclude that always the elements which have more than one complement in a lattice which when taken as ordered triplet ,do not follow distributive property?

Answer 4

“$x∨(y∧z)=(x∨y)∧(x∨z) $”

This is distributive property of lattices. If a lattice is a distributive lattice, then each element has at most one complement (ie, $0$ or $1$ complements)

In the given lattice, $p$ and $t$ have $1$ complement each. $q,$r and $s$ have two complements each.

In the triplet, even if one element has $0$ or $1$ complements, the distributive property is satisfied.

Hence, only triplet that isn't allowed is $(q,r,s)$

 

But hold on. The question says that the triplets are ordered. Hence, $(q,r,s)$ is different from $(r,s,q)$ and both won't work.

Total triplets that aren't favourable = $3!=6$

So, favourable triplets = $|total|-6$

 

$|total| \neq {^5C}_3$ because the elements are "not necessarily distinct".

$|total|=5*5*5=125$

 

So, favourable triplets = $125-6=119$

 

Probability of favourable triplets = $\frac{119}{125}$, which is greater than $\frac{1}{5}$ but smaller than $1$

 

So, Option D

Comments

VYAN_jy

try taking examples!

---

i think in the answer we have left out the case where the elements are repeating. 

---

@Deepak Poonia   sir please add this answer as usefull answer.