Combinatorics — Counting Functions with Constraints
PYP_JEE_ADV_2026_P2
Grade None
Question:
Let $\mathbb{N}$ denote the set of all positive integers. Consider the sets
$$A=\{1,2,3,4,5\} \quad\text{and}\quad B=\{1,2,3,4,5,6,7\}.$$
Let $S$ be the set of all functions $f:A\to B$ such that $f(2)\neq2$ and $f(4)\neq4$. Consider the set
$$T=\{f\in S:\text{there exists a function }g:B\to\mathbb{N}\text{ such that }g(f(x))=2^x\text{ for all }x\in A\}.$$
Then the number of elements in the set $T$ is __________.
Step-by-Step Solution
Key Concept: The existence of $g$ requires $f$ to be injective — distinct inputs must map to distinct outputs so $g$ can assign different powers of 2. Inclusion-exclusion then handles the forbidden values.
**Step 1: Condition for $g$ to exist**
For $g(f(x))=2^x$ to have a solution $g:B\to\mathbb{N}$, we need $f$ to be injective on $A$ (otherwise $f(x_1)=f(x_2)$ with $x_1\neq x_2$ would require $g$ to map one value to two different values of $2^x$).
**Step 2: Count injective functions from A to B**
Total injective $f:A\to B$: $7\times6\times5\times4\times3=2520$.
**Step 3: Apply inclusion-exclusion for $f(2)\neq2$ and $f(4)\neq4$**
Injective with $f(2)=2$: $6\times5\times4\times3=360$. Injective with $f(4)=4$: $360$. Injective with both: $5\times4\times3=60$. Valid (neither): $2520-360-360+60=1860$.
Correct Answer: 1860