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

@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.