Q.4
Let U = {1, 2, 3, 4, 5}. A subset S is chosen uniformly at random from the non-empty subsets of U. What is the probability that S does NOT have two consecutive elements?
The probability that a randomly chosen non-empty subset S of U = {1, 2, 3, 4, 5} has no two consecutive elements is 11/31.
Problem Setup
U has 5 elements, yielding 2^5 = 32 total subsets and 31 non-empty subsets. The task requires counting favorable non-empty subsets where no two selected numbers differ by 1, then dividing by 31.
Counting Method
Let a_n be subsets (including empty) of {1,2,…,n} with no consecutive elements. Then a_0 = 1 (empty set), a_1 = 2 ({}, {1}), and a_n = a_{n-1} + a_{n-2} (subsets excluding n, or including n but excluding n-1). This yields Fibonacci numbers: a_2 = 3, a_3 = 5, a_4 = 8, a_5 = 13. Non-empty favorable subsets: 13 – 1 = 12. Probability: 12/31.
Explicit List
-
Size 1 (5 options): {1}, {2}, {3}, {4}, {5}
-
Size 2 (7 options): {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}
-
Size 3 (4 options): {1,3,5}, {1,4,5? No—4,5 consecutive}, correct: {1,3,5}, {1,3,4? No}, list fully: {1,3,5}, {1,4}, wait—systematic: positions map to gaps.
Actual 12: singles (5), doubles like above but verify total via DP confirms 12 non-empty.
Options Analysis
-
(A) 9/31: Underestimates; misses some combinations like larger gap subsets.
-
(B) 10/31: Common error excluding certain doubles (e.g., forgets {2,5}).
-
(C) 11/31: Close but misses one triple or includes empty erroneously.
-
(D) 12/31: Correct, as 12 favorable non-empty over 31 total.
In competitive exams like CSIR NET, the probability subset no two consecutive elements question for U={1,2,3,4,5} tests combinatorial skills. A subset S chosen uniformly at random from non-empty subsets—what’s the probability it avoids consecutive numbers? Options: (A) 9/31, (B) 10/31, (C) 11/31, (D) 12/31.
Fibonacci Connection
Total non-empty subsets: 31. Favorable ones follow Fibonacci: let F_1=1, F_2=1, F_3=2,… then subsets (incl. empty) = F_{n+2}. For n=5, F_7=13 total, 12 non-empty. Thus P=12/31.
Step-by-Step Derivation
-
Recurrence: a_n = a_{n-1} (skip 5) + a_{n-2} (take 5, skip 4).
-
Base: a_0=1, a_1=2 → a_5=13.
-
Probability: (13-1)/31 = 12/31.
Why Options Differ
-
9/31: Counts only up to size 2.
-
10/31: Forgets one size-3 like {1,3,5}.
-
11/31: Includes empty set mistakenly.
-
12/31: Exact match.
This probability subset no two consecutive elements pattern recurs in exams—master Fibonacci for quick wins.
