Let $A$ be the set of all natural numbers less than or equal to $100$. How many relations can be defined in $A \times A$ such that (details inside)

Question

$A = \{x \le100, x \in \mathbb{N}\}$

How many relations $R \subseteq A \times A$ can be defined such that R is reflexive, R is symmetric and $(2,x) \in R \Leftrightarrow x $ is an even number

If you could explain step by step I'd be really grateful

Answer 1

Let's figure out which elements of $A \times A$ are bounded to be in or out of $R$, and which ones aren't.

• Because of the last condition, every couple of the form $(2, \: x)$ with $x$ even is necessarily in $R$; but then, because of the symmetry, $(x, \: 2)$ is in $R$ too.
• Since $R$ is reflexive, $(x, \: x)$ is always in $R$.
• Again from the last property, $(2, \: x) \not\in R$ whenever $x$ is odd. Also, because of the symmetry, $(x, \: 2) \not\in R$.
• We are left with the couples $(x, \: y)$ with $x \ne y$ and $x, \: y \ne 2$, for which we are (almost) arbitrarily allowed to decide whether they belong or not to $R$. The only condition that has to be satisfied is the symmetry, so $(x, \: y) \in R$ iff $(y, \: x) \in R$.

Summing up, the number of relations that satisfy all the conditions matches the number of ways in which we can choose, for every unordered couple $\{x, \: y\}$ with $x \ne y$ and $x, \: y \ne 2$ (and of course $1 \le x, \: y \le 100$), if $(x, \: y) \in R$ or $(x, \: y) \ne R$. Since such couples are $\displaystyle \binom{99}{2} = 4851$, the number of relations is $\boxed{2^{4851}}$.

Answer 2

Since $R$ is reflexive every pair on main diagonal is in $R$.

Since $R$ is symmetric the upper part over the main diagonal is uniquely determined by lover part under the main diagonal we must count free ''places'' in lover part. Since the pairs $(4,2),$ $(6,2)$,...$(100,2)$ are in lover part and the pairs $(2,1)$, $(3,2), (5,2)$,...,$(99,2)$ are not, we have ${100^2-100 \over 2} -99= 4851$ pairs to choose in lover part. Thus we have $2^{4851}$ relations $R$.

Answer 3

Well, let's think it out.

$A \times A$ have $100*100= 10000$ elements of which each either is or is not in the relationship. So there are $2^{10000}$ relations.

But it is symmetric. $(a,b)$ is in the relation if and only if $(b,a)$, so we don't so we only have to consider whether pairs $(a,b); a\le b$ are in the relationship. That will "force" whether $(b,a)$ is in.

There are $\sum_{i=1}^{100} i = 5050$ such pairs so there are $2^{5050}$ symetric relations. But the relation is also reflexive so all $(a,a)$ are forced to be in. So the only "free" pairs are $(a,b); a < b$ and there are are $100$ $(a,a)$ pairs so we have $5050 - 100 = 4950$ free pairs.

We also told that the pair $(2,x)$ is not free. It actually doesn't matter if $(2,x)$ is forced to be in or $(2,x)$ is force to be out. It is just that $(2,x)$ is forced. And if $(2,x)$ is forced so is $(x,2)$.

So let's review which pairs are free.

$(a,b)$ is free if i) $a \ne b$ [$(a,a)$ must be in] ii) wolog $a < b$. [If $a > b$ then $(a,b)$ is forced to be what $(b,a)$ is.] iii) neither $a$ nor $b$ is equal to $2$. [$(2,b)$ is forced to be in or out.]

So there are $\sum_{b=1;b\ne 2}^{100} |A=\{a|a<b; a\ne 2\}| =$

$\sum_{c=1}^{99} |D=\{d|d < c\}|$

$\sum_{c=1}^{99} (c-1)$

$\sum_{e=0}^{98} e = \frac {98*99}2 = 4851$

and the number of such relations is $2^{4851}$.

=====

I'm not going to change my answer but lashes with a wet noodle to me for viewing this in terms of summation rather than the more intuitive "choosing". In choosing a pair $(a,b)$ we are choosing two distinct terms (because $(a,a)$ must be in the relation) from $99$ choices ($2$ is omitted because $(2,x)$ and $(y,2)$ are forced to be in or out base on the other term) and order doesn't matter (because $(a,b)$ is in $\iff$ $(b,a)$ is in).

There are ${99\choose 2}=4851$ such pairs.

Same answer, same reason. But "choice" is maybe more intuitive and easy to follow than summation. (Although they are equivalent yet different models for the same thing.)