GATE 2020 CS Q.17: solution and answer

GATE 2020 · CSQ.17 · 1 mark · NAT

Let $R$ be the set of all binary relations on the set ${1, 2, 3}$ . Suppose a relation is chosen from $R$ at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The probability that the chosen relation is reflexive is $0.125$ .

Official answer: 0.125Source: Official answer key, GATE 2020 CS (IIT Delhi)

A binary relation on $A = {1, 2, 3}$ is a subset of $A \times A$ , and $∣ A \times A ∣ = 3 \times 3 = 9$ .
Each of the 9 ordered pairs is either in the relation or not, so the number of binary relations is $∣ R ∣ = 2^{9} = 512$ . Choosing at random makes each relation equally likely.
A relation is reflexive exactly when it contains $(1, 1)$ , $(2, 2)$ and $(3, 3)$ . These 3 pairs are forced.
The other $9 - 3 = 6$ pairs may each be present or absent, so the number of reflexive relations is $2^{6} = 64$ .
$P = \frac{64}{512} = \frac{1}{8} = 0.125.$

KEY IDEA

Count relations as subsets of $A \times A$ . Reflexivity fixes the $n$ diagonal pairs, leaving $2^{n^{2} - n}$ reflexive relations out of $2^{n^{2}}$ , so the probability is $2^{- n}$ . For $n = 3$ this is $1/8$ .

WATCH OUT FOR

Counting only $2^{3}$ relations, or forgetting that the 6 off-diagonal pairs are free. Another slip is treating the 3 diagonal pairs as optional, which gives the wrong ratio.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 8 Sets & relations questions, with notes

GATE 2020 CS Q.17: solution and answer

Answer and solution

More Sets & relations questions