Sets, Relations & Functions
Divisibility / Combinatorial Counting
nta_pyq_2025_apr
Grade 11
Question:
Let $S = \{p_1, p_2, \ldots, p_{10}\}$ be the set of first ten prime numbers. Let $A = S \cup P$, where $P$ is the set of all possible products of distinct elements of $S$. Then the number of all ordered pairs $(x, y)$, $x \in S$, $y \in A$, such that $x$ divides $y$, is ___
Step-by-Step Solution
Key Concept: For each prime $x = p_i \in S$, the elements $y \in A$ divisible by $p_i$ are: $p_i$ itself, and all products of distinct primes from $S$ that include $p_i$. The number of such products equals $2^9$ (choose any subset of the other 9 primes to multiply with $p_i$).
For each of the 10 primes $p_i$, it divides $y = p_i \times (\text{subset of other 9 primes})$: there are $2^9 = 512$ such $y$. Total ordered pairs $= 10 \times 512 = 5120$.
Correct Answer: 5120