How many pairs of sets (S, T) are possible among the subsets of {1, 2, 3, 4, 5, 6} that satisfy the condition that T is a subset of S? A. 729 B. 728 C. 60 D. 665

GATE 2023 · General Aptitude · Counting · medium

Answer: There are 3^6 = 729 ordered pairs (S, T) with T subset of S. Answer: A.

1. Identify membership states per element: For each element x in {1,2,3,4,5,6}, the possible membership states with respect to (S,T) where T subset S are: (1) x not in S (so x not in T), (2) x in S but not T, (3) x in both S and T. So each element independently has 3 states.
2. Multiply choices across all 6 elements: Total pairs (S, T) = 3 x 3 x 3 x 3 x 3 x 3 = 3^6 = 729.