Sets, Relations & Functions
Counting Functions with a Given Property
nta_pyq_2024_jan
Grade 11
Question:
Let $A=\{1,2,3,\ldots7\}$ and let $P(1)$ 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\mathbb{N}$ and $m$ is least, then $m+n$ is equal to
Step-by-Step Solution
Key Concept: For each element $a\in A$, $f(a)$ must be a subset of $A$ that contains $a$. The number of subsets of $A$ containing a fixed element $a$ is $2^6=64$ (the other 6 elements are free). Since choices for each element are independent, total $=(2^6)^7=2^{42}$.
For each of 7 elements: $2^6=64$ valid subsets. Total$=64^7=2^{42}$. So $m=2,n=42$. $m+n=44$.
Correct Answer: 44