# Sets

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.

2305
Shaswata Roy ·

If 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)}