2015 · Q34
Let A and B be finite non-empty sets with the number of elements in A = m and number of elements in B = n. Let m > n. If for some integer k > 1, the number of non-empty subsets of A = 2k + the number of non-empty subsets of B, then which one of the following is correct?
Elementary MathematicsSet Theory
- Am = n + 2
- Bm = n + 1
- Cm = n + p for some odd prime number p
- Dm = n+t for some composite number t
Explanation
Non-empty subsets: 2ᵍ − 1 = 2ᵏ + (2ⁿ − 1) gives 2ᵍ = 2ⁿ + 2ᵏ, i.e. 2ⁿ(2^{m−n} − 1) = 2ᵏ. Hence 2^{m−n} − 1 is a power of 2, forcing 2^{m−n} − 1 = 1, so m − n = 1, i.e. m = n + 1 (option B; '2k' in the text denotes 2ᵏ).