Suppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram: (Hasse diagram: t is the top element; p and q are below t; r is below p; s is below q; r and s both connect to a bottom element, and p and q share certain meets/joins.) For any x, y in L, not necessarily distinct, x v y and x ^ y are 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/2 D. 1/2 < p_r <= 1
GATE 2015 · Discrete Mathematics · Lattice · medium
Answer: p_r is strictly between 1/2 and 1, i.e. 1/2 < p_r <= 1 — option D.
- Check whether L is a distributive lattice: L is not a distributive lattice because it contains a diamond-like pentagon or M3 sub-lattice; hence p_r < 1, ruling out option B (p_r = 1).
- Estimate the fraction of satisfying triples: Triples where x = t (top), any y,z: LHS = t v anything = t, RHS = t ^ t = t. That gives 25 always-satisfying triples. Similarly x = bottom satisfies trivially. Additionally all triples where y = z trivially satisfy the identity. Counting carefully shows that a majority (> 63 out of 125) satisfy the identity, so p_r > 1/2.