RankRizz
JEE MAIN 2022 · 28 JUN S2+4 / −1HARDTRANSCRIBED

JEE Main 2022 Mathematics question — One-one, onto functions and counting functions

Let S={1,2,3,4}S = \{1, 2, 3, 4\}. Then the number of elements in the set {f:S×S→S:f\{f : S \times S \to S : f is onto and f(a,b)=f(b,a)≥a∀(a,b)∈S×S}f(a,b) = f(b,a) \geq a \forall (a,b) \in S \times S\} is

SOLUTION

We need to count functions f:S×S→Sf : S \times S \to S (where S={1,2,3,4}S = \{1,2,3,4\}) that are onto, symmetric (f(a,b)=f(b,a)f(a,b) = f(b,a)), and satisfy f(a,b)≥af(a,b) \geq a for all (a,b)∈S×S(a,b) \in S \times S.

Analyzing the constraint f(a,b)≥af(a,b) \geq a, since f(a,b)=f(b,a)f(a,b) = f(b,a), we also need f(a,b)≥bf(a,b) \geq b. Therefore:

f(a,b)≥max⁡(a,b)f(a,b) \geq \max(a,b)

Next, because f(a,b)∈S={1,2,3,4}f(a,b) \in S = \{1,2,3,4\} and f(a,b)≥max⁡(a,b)f(a,b) \geq \max(a,b), we have f(4,b)≥4f(4,b) \geq 4 for all bb, so f(4,b)=4f(4,b) = 4. Similarly, f(a,4)=4f(a,4) = 4. This fixes all values involving 4.

Now consider values involving only {1,2,3}\{1,2,3\}. For (a,b)(a,b) with a,b∈{1,2,3}a,b \in \{1,2,3\}, we have f(a,b)≥max⁡(a,b)f(a,b) \geq \max(a,b). Since ff is symmetric, we only need to specify f(a,b)f(a,b) for a≤ba \leq b.

f(3,3)≥3f(3,3) \geq 3: choices are {3,4}\{3,4\} (2 choices)

f(2,3)=f(3,2)≥3f(2,3) = f(3,2) \geq 3: choices are {3,4}\{3,4\} (2 choices)

f(1,3)=f(3,1)≥3f(1,3) = f(3,1) \geq 3: choices are {3,4}\{3,4\} (2 choices)

f(2,2)≥2f(2,2) \geq 2: choices are {2,3,4}\{2,3,4\} (3 choices)

f(1,2)=f(2,1)≥2f(1,2) = f(2,1) \geq 2: choices are {2,3,4}\{2,3,4\} (3 choices)

f(1,1)≥1f(1,1) \geq 1: choices are {1,2,3,4}\{1,2,3,4\} (4 choices)

Without the onto constraint, the total number of assignments is 2×2×2×3×3×4=2882 \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)f(1,1), so f(1,1)=1f(1,1) = 1 is forced. This reduces choices for f(1,1)f(1,1) to 1 option.

Value 2 can appear at f(1,2)f(1,2) or f(2,2)f(2,2), and it must appear in at least one of those entries.

Value 3 can appear at f(3,3)f(3,3), f(2,3)f(2,3), f(1,3)f(1,3), f(2,2)f(2,2), or f(1,2)f(1,2).

With f(1,1)=1f(1,1) = 1, the remaining free choices are:

f(3,3)f(3,3): {3,4}\{3,4\}, f(2,3)f(2,3): {3,4}\{3,4\}, f(1,3)f(1,3): {3,4}\{3,4\}, f(2,2)f(2,2): {2,3,4}\{2,3,4\}, f(1,2)f(1,2): {2,3,4}\{2,3,4\}.

Without the onto requirement for 2 and 3, there are 2×2×2×3×3=722 \times 2 \times 2 \times 3 \times 3 = 72 assignments.

To ensure both 2 and 3 appear, we use inclusion-exclusion. Let AA be the set of assignments where 2 does not appear, and BB the set where 3 does not appear.

In AA, we must have f(1,2)∈{3,4}f(1,2) \in \{3,4\} and f(2,2)∈{3,4}f(2,2) \in \{3,4\}, giving ∣A∣=2×2×2×2×2=32|A| = 2 \times 2 \times 2 \times 2 \times 2 = 32.

In BB, we must have f(3,3)=f(2,3)=f(1,3)=4f(3,3) = f(2,3) = f(1,3) = 4 and f(2,2),f(1,2)∈{2,4}f(2,2), f(1,2) \in \{2,4\}, giving ∣B∣=1×1×1×2×2=4|B| = 1 \times 1 \times 1 \times 2 \times 2 = 4.

In A∩BA \cap B, both 2 and 3 are absent, so all five free values must be 4, giving ∣A∩B∣=1|A \cap B| = 1.

By inclusion-exclusion, the number of valid assignments is 72−32−4+1=3772 - 32 - 4 + 1 = 37.

The answer is 37\boxed{37}.

Tagged One-one, onto functions and counting functions. Machine-assigned, so read it as a strong shortlist rather than a verdict.

ChapterFunctions
TopicOne-one, onto functions and counting functions
TypeNumerical answer