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

Easy approch
In such questions, a quick way is to check extreme elements.
https://gateoverflow.in/8281/gate-cse-2015-set-1-question-34?show=526577#a526577

---

You can solve this question quickly by counting the combinations that does not satisfy the distributive property,
the middle 3 elements q, r, s and it's permutations don't satisfy the property,
There are 125 total combinations with repetition,
125 - 6 (3! ways of arranging middle elements that does not satisfy the property) = 119
119/125 > 1/5 so Option D is right

correct me if i am wrong

---

@architha joshi699 In Pentagon it is very complicated than Kite lattice, if you find anything pelase share it here.

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

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

---

Nice  explanation sir .

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

---

@KartikGawande I think taking all elements same is a trivial case. Meanwhile @Wali 's ans. is always true for non trivial cases (x!=y!=z)

---

nice

---

This is the best answer for this Question, Chatgpt also says the same.

Answer 3

“$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

@JashanArora

Mind Blowing Answer

---

@JashanArora 

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

What is source of this line? Also, does it hold on every lattice?

---

Best answer

Answer 4

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 5

here , short cut to this question

by watching figure u can guess that it's not distributive lattice, becoz for q there is 2 complement so , it cant satisfy distributive property , therefore, probability cant be 1 , so option (a) is wrong

now if u apply distributive property for any 3 elements which are in straight line they will satisfy the distributive property , it concludes that its probability cant be 0, therefore option (b) is wrong

now no of possible distributive equation will be 5*5*5=125 because repetition is allowed here. since in above line, i hav proved that elements in straight line will follow the distributive prop then no of possible distributive with 3 element is 3*3*3=27 (since repeatition is allowed , u might ask question that there are 5 elements then why 3 ? since we have to fix 2 as universal lower bound and upper bound ) so 27/125 is greater than 1/5

 

so d option is correct

Answer 6

Use Extreme Elements

In such questions, a quick way is to check extreme elements. Let the set of elements in the lattice be $S = \{p, q, r, s, t\}$, where $|S| = 5$.

 

Take $x = t$ (Top Element):

For any $y, z \in S$:

$$x \vee (y \wedge z) = t \vee (y \wedge z) = t$$

$$(x \vee y) \wedge (x \vee z) = t \wedge t = t$$

Since LHS = RHS, all $5 \times 5 = 25$ triplets where $x=t$ are valid.

 

Take $x = p$ (Bottom Element):

For any $y, z \in S$:

$$x \vee (y \wedge z) = p \vee (y \wedge z) = y \wedge z$$

$$(x \vee y) \wedge (x \vee z) = y \wedge z$$

Again, all $25$ triplets where $x=p$ are valid.

Total valid triplets:

$$\text{Count} \ge 25 + 25 = 50$$

Total possible triplets:

$$5^3 = 125$$

Thus:

$$p_r \ge \frac{50}{125} = \frac{2}{5}$$

 

Why not $p_r = 1$?

To have $p_r = 1$, the identity must hold for all triplets (i.e., the lattice must be distributive). We only need one counterexample to reject this.

Take $x = r, y = q, z = s$:

Given $q \wedge s = p$:

• LHS: $r \vee (q \wedge s) = r \vee p = r$

• RHS: $(r \vee q) \wedge (r \vee s) = t \wedge t = t$

Since $r \neq t$, the identity fails for this triplet.

 

Conclusion

• At least $50$ valid cases $\implies p_r \ge \frac{2}{5}$

• Not always true $\implies p_r < 1$

Therefore:

$$\boxed{\frac{1}{5} < p_r < 1}$$

Answer is option D

Comments

@Het2312 Hey it's a nice approach, does the extreme cases always holds valid? in all the latices ?

---

@S_Sandeep yes it's always hold. if you see my answer i write it in generalized way. there is no perticular value selected for top and bottom element