JEE Advanced 1981

LEVELBoard

Animated Solution for Mathematics - Sets and Relations: Suppose $A_{1}, A_{2}, \dots, A_{30}$ are thirty sets each with five elements and $B_{1}, B_{2}, \dots, B_{n}$ are $n$ sets each with three elements. Let $⋃_{i = 1}^{30} A_{i} = ⋃_{j = 1}^{n} B_{j} = S$ . Assume that each element of $S$ belongs to exactly ten of the $A_{i}$ 's and to exactly nine of the $B_{j}$ 's. Find $n$ .

Enter Numerical Value:

Visualized Solution

Visualizing the Union Set $S$

We are given two families of sets: ${A_{1}, A_{2}, \dots, A_{30}}$ and ${B_{1}, B_{2}, \dots, B_{n}}$ .
The union of all $A_{i}$ sets is equal to the union of all $B_{j}$ sets, which defines our universal set $S$ .
Mathematically: $⋃_{i = 1}^{30} A_{i} = ⋃_{j = 1}^{n} B_{j} = S$ .

Properties of the $A_{i}$ Sets

There are exactly $30$ sets in the family $A_{i}$ (where $i = 1, 2, \dots, 30$ ).
Each of these sets contains exactly $5$ elements: $n (A_{i}) = 5$ for all $i$ .
If we list all elements of all $A_{i}$ sets with their repetitions, the total count is $30 \times 5 = 150$ .

Properties of the $B_{j}$ Sets

Similarly, we have $n$ sets in the family $B_{j}$ (where $j = 1, 2, \dots, n$ ).
Each of these sets contains exactly $3$ elements: $n (B_{j}) = 3$ for all $j$ .
The total number of elements in this family, including repetitions, is $n \times 3 = 3 n$ .

Understanding Element Membership

Let's pick an arbitrary element $x$ belonging to the union set $S$ .
We are told that $x$ belongs to exactly $10$ of the $A_{i}$ sets.
This means that in our raw count of all elements across all $A_{i}$ sets, this single element $x$ is counted exactly $10$ times.

The Double Counting Principle

If every element in $S$ is counted exactly $k$ times when we sum the sizes of all sets, then:
$\sum n (A_{i}) = k \times n (S)$
Therefore, the actual number of unique elements in $S$ is:
$n (S) = \frac{\sum _{i = 1}^{30} n ( A _{i} )}{10}$

Finding the Size of Set $S$

Let's substitute the values for family $A_{i}$ :
Sum of elements with repetition $= 30 \times 5 = 150$ .
Since each element is repeated exactly $10$ times, we divide by $10$ :
$n (S) = \frac{150}{10} = 15$ .

Connecting to the $B_{j}$ Sets

Now let's look at the same element $x$ from the perspective of the $B_{j}$ sets.
We are given that each element of $S$ belongs to exactly $9$ of the $B_{j}$ sets.
This means every unique element in $S$ is counted exactly $9$ times in the sum of the sizes of all $B_{j}$ sets.

Expressing $n (S)$ in terms of $n$

The sum of the sizes of all $B_{j}$ sets is $n \times 3 = 3 n$ .
Since each element is repeated exactly $9$ times, the number of unique elements in $S$ is:
$n (S) = \frac{3 n}{9} = \frac{n}{3}$ .

Solving for $n$

Since both expressions represent the exact same quantity, $n (S)$ , we can set them equal to each other:
$\frac{n}{3} = 15$
Multiplying both sides by $3$ , we get:
$n = 15 \times 3 = 45$ .

Key Takeaway & Verification

The total number of sets $B_{j}$ is $n = 45$ .
Verification: If $n = 45$ , total elements in $B_{j}$ with repetition is $45 \times 3 = 135$ .
Dividing by the repetition factor of $9$ gives $135/9 = 15$ , which perfectly matches $n (S) = 15$ .

00:00 / 00:00

The Sigma Insight: Types of Sets and Set Operations

Solution Diagram

Analyzing the Setup

We are given two collections of sets,

A_{1}, A_{2}, \dots, A_{30}

and

B_{1}, B_{2}, \dots, B_{n}

, all defined within a universal set

S

. Each set

A_{i}

contains 5 elements, and each set

B_{j}

contains 3 elements.

Instead of attempting to identify individual elements, we utilize the Double Counting Principle. This method allows us to relate the total number of "slots" filled by the elements to the size of the universal set

S

Calculating the Size of $S$ via Set $A$

First, we calculate the total number of slots occupied by the sets

A_{i}

. Since there are 30 sets, each containing 5 elements, the total number of slots is:

30 \times 5 = 150

The problem states that every element in

S

is counted exactly 10 times across these sets. Therefore, the size of the universal set

∣ S ∣

is given by:

∣ S ∣ = \frac{150}{10} = 15

Applying the Principle to Set $B$

Next, we apply the same logic to the collection of sets

B_{j}

. There are

n

sets, each containing 3 elements, resulting in a total of

3 n

slots.

Given that each element in

S

is counted exactly 9 times in this collection, we express the size of

S

as:

∣ S ∣ = \frac{3 n}{9} = \frac{n}{3}

Final Calculation

Since both expressions represent the same universal set

S

, we equate the two results:

\frac{n}{3} = 15

Solving for

n

, we find:

$n = 45$

This elegant application of the Double Counting Principle demonstrates that complex combinatorial problems can often be resolved by focusing on the symmetry of the underlying structure rather than the specific elements themselves.

Common Traps & FAQs

Why can't we just find the intersection of the sets? How do we know which elements are in which sets?

That is the beauty of this problem! You do not need to know the specific intersection structure. The problem gives you the aggregate membership count, which is all you need. We are counting the 'slots' and dividing by the 'repetition factor'. It is a classic combinatorial shortcut that bypasses the need for complex set diagrams.

Why do we divide by 10 and 9? I feel like I should be multiplying.

Think of it this way: if you count an object 10 times, you have over-counted it by a factor of 10. To get the true count of the object, you must divide by that factor. If you have 150 'instances' of elements, and each unique element appears 10 times, you must divide 150 by 10 to find the number of unique elements. It is the inverse of the counting process.

Is there a formal name for this technique? Is it the Principle of Inclusion-Exclusion?

It is actually simpler than the Principle of Inclusion-Exclusion! This is known as the 'Double Counting Principle' or 'Fubini's Principle' in combinatorics. It is a powerful method where you count the same quantity in two different ways to establish an equality. It is a staple tool for JEE Advanced problems involving set theory.

Enter Numerical Value:

Visualized Solution

Visualizing the Union Set $S$

Properties of the $A_{i}$ Sets

Properties of the $B_{j}$ Sets

Understanding Element Membership

The Double Counting Principle

Finding the Size of Set $S$

Connecting to the $B_{j}$ Sets

Expressing $n (S)$ in terms of $n$

Solving for $n$

Key Takeaway & Verification

The Sigma Insight: Types of Sets and Set Operations

Analyzing the Setup

Calculating the Size of $S$ via Set $A$

Applying the Principle to Set $B$

Final Calculation

Similar Questions

Let $\cup_{i = 1}^{50} X_{i} = \cup_{i = 1}^{n} Y_{i} = T$ , where each $X_{i}$ contains 10 elements and each $Y_{i}$ contains 5 elements. If each element of the set $T$ is an element of exactly 20 of sets $X_{i}$ 's and exactly 6 of sets $Y_{i}$ 's then $n$ is equal to

Let $X = {n \in N : 1 \leq n \leq 50}$ . If $A = {n \in X : n is a multiple of 2}$ and $B = {n \in X : n is a multiple of 7}$ , then the number of elements in the smallest subset of $X$ containing both $A$ and $B$ is

Set $A$ has $m$ elements and Set $B$ has $n$ elements. If the total number of subsets of $A$ is 112 more than the total number of subsets of $B$ , then the value of $m \cdot n$ is

Let $A = {1, 2, 3, 4, 5, 6, 7}$ and $B = {3, 6, 7, 9}$ . Then the number of elements in the set ${C \subseteq A : C \cap B \neq = \emptyset}$ is ________

Let $A : {1, 2, 3, 4, 5, 6, 7}$ . Define $B = {T \subseteq A : either 1 \in / T or 2 \in / T}$ and $C = {T \subseteq A : the sum of all the elements of T is a prime number}$ . Then the number of elements in the set $B \cup C$ is ________

(i) Set $A$ has 3 elements, and set $B$ has 6 elements. What can be the minimum number of elements in the set $A \cup B$ ? (ii) $P, Q, R$ are subsets of a set $A$ . Is the following equality true? $R \times (P^{c} \cup Q^{c})^{c} = (R \times P) \cap (R \times Q)$ ?

Let A and B be two sets containing four and two elements respectively. Then the number of subsets of the set $A \times B$ , each having at least three elements is :

Let $A = {n \in N : H.C.F. (n, 45) = 1}$ and Let $B = {2 k : k \in {1, 2, \dots, 100}}$ . Then the sum of all the elements of $A \cap B$ is ________.

Let $A = {1, 2, 3, \dots, 7}$ and let $P (A)$ denote the power set of $A$ . If the number of functions $f : A \to P (A)$ such that $a \in f (a), \forall a \in A$ is $m^{n}, m$ and $n \in N$ and $m$ is least, then $m + n$ is equal to ______

Let $S = {4, 6, 9}$ and $T = {9, 10, 11, \dots, 1000}$ . If $A = {a_{1} + a_{2} + \dots + a_{k} : k \in N, a_{1}, a_{2}, \dots, a_{k} \in S}$ , then the sum of all the elements in the set $T - A$ is equal to ______.

Enter Numerical Value:

Visualized Solution

Visualizing the Union Set .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } S

Properties of the .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Ai​ Sets

Properties of the .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Bj​ Sets

Understanding Element Membership

The Double Counting Principle

Finding the Size of Set .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } S

Connecting to the .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Bj​ Sets

Expressing .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } n(S) in terms of .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } n

Solving for .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } n

Key Takeaway & Verification

The Sigma Insight: Types of Sets and Set Operations

Analyzing the Setup

Calculating the Size of .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } S via Set .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A

Applying the Principle to Set .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B

Final Calculation

Similar Questions

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Set A has m elements and Set B has n elements. If the total number of subsets of A is 112 more than the total number of subsets of B, then the value of m⋅n is

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let A={1,2,3,4,5,6,7} and B={3,6,7,9}. Then the number of elements in the set {C⊆A:C∩B=∅} is ________

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let A and B be two sets containing four and two elements respectively. Then the number of subsets of the set A×B, each having at least three elements is :

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let A={n∈N:H.C.F.(n,45)=1} and Let B={2k:k∈{1,2,…,100}}. Then the sum of all the elements of A∩B is ________.

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let S={4,6,9} and T={9,10,11,…,1000}. If A={a1​+a2​+⋯+ak​:k∈N,a1​,a2​,…,ak​∈S}, then the sum of all the elements in the set T−A is equal to ______.

Visualizing the Union Set $S$

Properties of the $A_{i}$ Sets

Properties of the $B_{j}$ Sets

Finding the Size of Set $S$

Connecting to the $B_{j}$ Sets

Expressing $n (S)$ in terms of $n$

Solving for $n$

Calculating the Size of $S$ via Set $A$

Applying the Principle to Set $B$

Set $A$ has $m$ elements and Set $B$ has $n$ elements. If the total number of subsets of $A$ is 112 more than the total number of subsets of $B$ , then the value of $m \cdot n$ is

Let $A = {1, 2, 3, 4, 5, 6, 7}$ and $B = {3, 6, 7, 9}$ . Then the number of elements in the set ${C \subseteq A : C \cap B \neq = \emptyset}$ is ________

Let A and B be two sets containing four and two elements respectively. Then the number of subsets of the set $A \times B$ , each having at least three elements is :

Let $A = {n \in N : H.C.F. (n, 45) = 1}$ and Let $B = {2 k : k \in {1, 2, \dots, 100}}$ . Then the sum of all the elements of $A \cap B$ is ________.

Let $S = {4, 6, 9}$ and $T = {9, 10, 11, \dots, 1000}$ . If $A = {a_{1} + a_{2} + \dots + a_{k} : k \in N, a_{1}, a_{2}, \dots, a_{k} \in S}$ , then the sum of all the elements in the set $T - A$ is equal to ______.