Let R=(x,y) N N: _e(x+y) 2.

Question

Let $R={(x,y)\in N	imes N:{\log }_{e}(x+y)\le 2}$. Then the minimum number of elements, required to be added in $R$ to make it a transitive relation, is $____$ .

Answer: 15

Accepted Answer

We have

$R={(x,y)\in N	imes N:\ln (x+y)\le 2}.$

To make the relation transitive, we first find all pairs already in $R$.

Since

$\ln (x+y)\le 2\, \iff \, x+y\le {e}^{2}.$

Now,

${e}^{2}\approx 7.389.$

So, for natural numbers $x,y$, we must have

$x+y\le 7.$

Hence,

$R={(x,y)\in N	imes N:x+y\le 7}.$

Now list all such pairs:

For $x=1$: $(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)$

For $x=2$: $(2,1),(2,2),(2,3),(2,4),(2,5)$

For $x=3$: $(3,1),(3,2),(3,3),(3,4)$

For $x=4$: $(4,1),(4,2),(4,3)$

For $x=5$: $(5,1),(5,2)$

For $x=6$: $(6,1)$

So these are the elements of $R$.

A relation is transitive if whenever

$(a,b)\in R\, \, (b,c)\in R,$

then

$(a,c)\in R.$

We need to find all pairs $(a,c)$ that must be present because of transitivity.

Find which middle elements are possible: If $(a,b)\in R$, then

$a+b\le 7.$

If $(b,c)\in R$, then

$b+c\le 7.$

For a fixed $b$, this gives

$a\le 7-b,\, c\le 7-b.$

So for each $b$, transitivity demands that all pairs

$(a,c)\, 1\le a\le 7-b,\, 1\le c\le 7-b$

must be in the relation.

Taking union over all possible $b\in N$ with at least one such pair, we get:

For $b=1$: required pairs are all

$(a,c),\, 1\le a\le 6,\, 1\le c\le 6.$

This is already the largest possible set forced by transitivity.

So, if relation is to be transitive, it must contain every pair

$(a,c)\in {1,2,3,4,5,6}	imes {1,2,3,4,5,6}.$

That means the transitive closure must at least contain all $36$ pairs

$(a,c),\, 1\le a,c\le 6.$

Count how many of these are already in $R$: Among these $36$ pairs, $R$ already contains those with

$a+c\le 7.$

Count them:

$a=1$: $c=1$ to $6$ $\Rightarrow 6$

$a=2$: $c=1$ to $5$ $\Rightarrow 5$

$a=3$: $c=1$ to $4$ $\Rightarrow 4$

$a=4$: $c=1$ to $3$ $\Rightarrow 3$

$a=5$: $c=1$ to $2$ $\Rightarrow 2$

$a=6$: $c=1$ $\Rightarrow 1$

Total:

$6+5+4+3+2+1=21.$

So the number of additional pairs needed is

$36-21=15.$

Check that this is sufficient: If we add all missing pairs among

${1,2,3,4,5,6}	imes {1,2,3,4,5,6},$

then the relation becomes

${(a,c):1\le a\le 6,\, 1\le c\le 6}.$

This is clearly transitive, because whenever

$(a,b)\in R\, \, (b,c)\in R,$

all three numbers lie in ${1,2,3,4,5,6}$, so $(a,c)$ is also in the relation.

Therefore, the minimum number of elements to be added is

$15$

Solutions · 1