Sign in
Please select an account to continue using cracku.in
↓ →
Join Our JEE Preparation Group
Prep with like-minded aspirants; Get access to free daily tests and study material.
Let $$S = \{1, 2, 3, 4\}$$. Then the number of elements in the set $$\{f : S \times S \to S : f$$ is onto and $$f(a,b) = f(b,a) \geq a \forall (a,b) \in S \times S\}$$ is
Correct Answer: 37
We need to count functions $$f : S \times S \to S$$ (where $$S = \{1,2,3,4\}$$) that are onto, symmetric ($$f(a,b) = f(b,a)$$), and satisfy $$f(a,b) \geq a$$ for all $$(a,b) \in S \times S$$.
Analyzing the constraint $$f(a,b) \geq a$$, since $$f(a,b) = f(b,a)$$, we also need $$f(a,b) \geq b$$. Therefore:
$$f(a,b) \geq \max(a,b)$$
Next, because $$f(a,b) \in S = \{1,2,3,4\}$$ and $$f(a,b) \geq \max(a,b)$$, we have $$f(4,b) \geq 4$$ for all $$b$$, so $$f(4,b) = 4$$. Similarly, $$f(a,4) = 4$$. This fixes all values involving 4.
Now consider values involving only $$\{1,2,3\}$$. For $$(a,b)$$ with $$a,b \in \{1,2,3\}$$, we have $$f(a,b) \geq \max(a,b)$$. Since $$f$$ is symmetric, we only need to specify $$f(a,b)$$ for $$a \leq b$$.
$$f(3,3) \geq 3$$: choices are $$\{3,4\}$$ (2 choices)
$$f(2,3) = f(3,2) \geq 3$$: choices are $$\{3,4\}$$ (2 choices)
$$f(1,3) = f(3,1) \geq 3$$: choices are $$\{3,4\}$$ (2 choices)
$$f(2,2) \geq 2$$: choices are $$\{2,3,4\}$$ (3 choices)
$$f(1,2) = f(2,1) \geq 2$$: choices are $$\{2,3,4\}$$ (3 choices)
$$f(1,1) \geq 1$$: choices are $$\{1,2,3,4\}$$ (4 choices)
Without the onto constraint, the total number of assignments is $$2 \times 2 \times 2 \times 3 \times 3 \times 4 = 288$$.
The value 4 is already achieved from the forced values. We need the values 1, 2, and 3 to each appear at least once.
Value 1 can only appear at $$f(1,1)$$, so $$f(1,1) = 1$$ is forced. This reduces choices for $$f(1,1)$$ to 1 option.
Value 2 can appear at $$f(1,2)$$ or $$f(2,2)$$, and it must appear in at least one of those entries.
Value 3 can appear at $$f(3,3)$$, $$f(2,3)$$, $$f(1,3)$$, $$f(2,2)$$, or $$f(1,2)$$.
With $$f(1,1) = 1$$, the remaining free choices are:
$$f(3,3)$$: $$\{3,4\}$$, $$f(2,3)$$: $$\{3,4\}$$, $$f(1,3)$$: $$\{3,4\}$$, $$f(2,2)$$: $$\{2,3,4\}$$, $$f(1,2)$$: $$\{2,3,4\}$$.
Without the onto requirement for 2 and 3, there are $$2 \times 2 \times 2 \times 3 \times 3 = 72$$ assignments.
To ensure both 2 and 3 appear, we use inclusion-exclusion. Let $$A$$ be the set of assignments where 2 does not appear, and $$B$$ the set where 3 does not appear.
In $$A$$, we must have $$f(1,2) \in \{3,4\}$$ and $$f(2,2) \in \{3,4\}$$, giving $$|A| = 2 \times 2 \times 2 \times 2 \times 2 = 32$$.
In $$B$$, we must have $$f(3,3) = f(2,3) = f(1,3) = 4$$ and $$f(2,2), f(1,2) \in \{2,4\}$$, giving $$|B| = 1 \times 1 \times 1 \times 2 \times 2 = 4$$.
In $$A \cap B$$, both 2 and 3 are absent, so all five free values must be 4, giving $$|A \cap B| = 1$$.
By inclusion-exclusion, the number of valid assignments is $$72 - 32 - 4 + 1 = 37$$.
The answer is $$\boxed{37}$$.
Create a FREE account and get:
Predict your JEE Main percentile, rank & performance in seconds
Educational materials for JEE preparation
Ask our AI anything
AI can make mistakes. Please verify important information.
AI can make mistakes. Please verify important information.