Suppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram (t is the top element, p is the bottom element, and q, r, s are three incomparable elements each lying between p and t). For any x, y in L, not necessarily distinct, x v y and x ^ y are the join and meet of x, y respectively. Let L^3 = {(x, y, z): x, y, z in L} be the set of all ordered triplets of the elements of L. Let p_r be the probability that an element (x, y, z) in L^3 chosen equiprobably satisfies x v (y ^ z) = (x v y) ^ (x v z). Then A. p_r = 0 B. p_r = 1 C. 0 < p_r <= 1/5 D. 1/5 < p_r < 1

GATE 2015 · Discrete Mathematics · Lattice · medium

Answer: L is the non-distributive M3 lattice, so the distributive identity holds for most but not all of the 125 triplets, placing p_r strictly in (1/5, 1): option D.

1. Identify the lattice as the non-distributive M3: The three middle atoms q, r, s are pairwise incomparable with meet p and join t. Test x = q, y = r, z = s: LHS = q v (r ^ s) = q v p = q; RHS = (q v r) ^ (q v s) = t ^ t = t. Since q != t the identity FAILS for this triple, so L is not distributive and therefore p_r != 1, eliminating option B.
2. Show the identity holds for many triples, so p_r is a large fraction: Whenever x = t the identity reads t = t ^ t = t (true); whenever x = p it reduces to y ^ z = y ^ z (true); equalities among x, y, z also make both sides agree. Such triples number in the dozens, so the count of favourable triples among the 125 is well above 25 (= 1/5 of 125) yet below 125. Hence p_r is strictly between 1/5 and 1, giving option D. (Counting carefully gives the favourable fraction comfortably inside this band.)