GATE 2024 CS1 Q.32: solution and answer

Official answer: 2Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. A bijection between two finite sets exists exactly when they have the same number of elements. From (i), $|A|=|B|=n$ with $n\ge 1$, since the sets are non-empty.

2. From (ii), $|A\times A|=|A\cup B|$, so $|A\cup B|=n^2$.

3. For any two finite sets, $\max (|A|,|B|)\le |A\cup B|\le |A|+|B|$. Here this reads $n\le |A\cup B|\le 2n$.

4. Combining, $n\le n^2\le 2n$. The left inequality holds for every $n\ge 1$. Dividing the right inequality by $n>0$ gives $n\le 2$. So $n\in \{1,2\}$.

5. Check $n=1$: take $A=B=\{a\}$. Then $|A\cup B|=1=1^2$, and bijections $A\to B$ and $A\times A\to A\cup B$ both exist. Valid.

6. Check $n=2$: take $A=\{1,2\}$ and $B=\{3,4\}$, which are disjoint. Then $|A\cup B|=4=2^2$, and both bijections exist. Valid.

7. Hence $|A|$ can be $1$ or $2$ and nothing else, so there are $2$ possible values.