Permutations & CombinationshardFree

Ordered pairs of subsets with max(X) greater than min(Y) | JEE Advanced

JEE Maths question with a full step-by-step solution.

Question
Suppose AA is the set of the first 33 natural numbers. Taking XX, YY as non-empty subsets of AA, the number of ordered set pairs (X,Y)\left(X,Y\right) such that max⁡(X)>min⁡(Y)\max\left(X\right)>\min\left(Y\right) is 2p2^{p}; then pp is equal to
Solution
Answer: 5
Step 1: Write n=∣A∣n = \left|A\right| and count the complementary event max⁡(X)≤min⁡(Y)\max\left(X\right) \le \min\left(Y\right). Fixing m=max⁡(X)m = \max\left(X\right), the set XX must contain mm and may contain any of 1,…,m−11,\ldots,m-1:
2 m−1 choices2^{\,m-1}\ \text{choices}
 Step 2: min⁡(Y)≥m\min\left(Y\right) \ge m means YY is a non-empty subset of {m,m+1,…,n}\left\{m,m+1,\ldots,n\right\}, a set of n−m+1n-m+1 elements:
2 n−m+1−1 choices2^{\,n-m+1}-1\ \text{choices}
 Each admissible pair has exactly one value of mm, so summing over mm counts every pair once:
#{max⁡X≤min⁡Y}=∑m=1n2 m−1(2 n−m+1−1)=∑m=1n(2n−2 m−1)=n2n−(2n−1)\#\left\{\max X \le \min Y\right\} = \sum_{m=1}^{n}2^{\,m-1}\left(2^{\,n-m+1}-1\right) = \sum_{m=1}^{n}\left(2^{n}-2^{\,m-1}\right) = n2^{n}-\left(2^{n}-1\right)
 Step 3: The total number of ordered pairs of non-empty subsets is (2n−1)2\left(2^{n}-1\right)^2, so
#{max⁡X>min⁡Y}=(2n−1)2−n2n+2n−1\#\left\{\max X>\min Y\right\} = \left(2^{n}-1\right)^2-n2^{n}+2^{n}-1
=22n−2 n+1+1−n2n+2n−1=22n−2n(n+1)=2n(2n−n−1)= 2^{2n}-2^{\,n+1}+1-n2^{n}+2^{n}-1 = 2^{2n}-2^{n}\left(n+1\right) = 2^{n}\left(2^{n}-n-1\right)
 Step 4: Putting n=3n = 3,
23(23−3−1)=8×4=32=252^{3}\left(2^{3}-3-1\right) = 8\times4 = 32 = 2^{5}
2p=32⟹p=52^{p} = 32 \quad\Longrightarrow\quad p = 5
 Distinct powers of 22 are unequal, so p=5p = 5 is the only value. (Direct enumeration over the 7×7=497\times7 = 49 ordered pairs of non-empty subsets of {1,2,3}\left\{1,2,3\right\} confirms 3232.) Answer: 55
Still stuck on this question?Ask your doubt on WhatsApp
Similar questions
Permutations & Combinations · medium
The number of seven-digit numbers that can be formed by using the digits 1,2,3,51, 2, 3, 5 and 77 such that each digit is used at least once, is
Permutations & Combinations · medium
A box contains 5 blue, 6 yellow and 4 red balls. The number of ways of drawing 8 balls containing at least two balls of each colour is:
Permutations & Combinations · medium
Two players AA and BB play a series of games of badminton. The player who wins 55 games first wins the series. Assuming no game ends in a draw, the number of ways in which player AA wins the series is
Permutations & Combinations · medium
The number of ways of forming a queue of 44 boys and 33 girls such that all the girls are not together, is

Solve more, learn faster

Sign up free to solve more JEE Maths questions and explore doMath — timed drills, mastery sprints, bookmarks, and chapter-wise progress tracking.

Sign up freeExplore doMath