Let S={1,2,3,...,n} and A={(a,b)l1≤a,b≤n}=S X S. A subset B of A is said to be a good subset if (x,x) belongs to B for every x belonging to S. Then the number of good subsets of A is
A. 1 B. 2n C.2n(n-1) D.2n2
The answer is C and it can be easily arrived at if we put n=1. But I want the solution.
-
UP 0 DOWN 0 0 1
1 Answers
2305If I am not mistaken this question is from KVPY 2012.
The number of tuples (a,b) is n2(since there are n ways to chose a and n ways to chose b).
Out of these n2 pairs B must contain n of these pairs of the form(x,x).
We are left with n(n-1) pairs.For each pair,there are 2 options-B may or may not have that pair.
Hence the number of good subsets=
2\times 2\times 2\times \cdots = 2^{n(n-1)}
Soumyadeep Basu Thanks.Upvote·0· Reply ·2013-10-24 01:27:13