in Set Theory & Algebra edited by
16,375 views
85 votes
85 votes

Consider a set $U$ of $23$ different compounds in a chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U$. Consider the following statements:

  1. Each compound in U \ S reacts with an odd number of compounds.
  2. At least one compound in U \ S reacts with an odd number of compounds.
  3. Each compound in U \ S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

  1. Only I
  2. Only II
  3. Only III
  4. None.
in Set Theory & Algebra edited by
16.4k views

4 Comments

same doubt !

if it is assumed then the answer will be D)none

0
0

@Harpuneet Kalsi @Pranavpurkar if react with themselves the there will be no problem as self loop make deg + 2 so, it's can not change degree if w/o self loop degree is even the even + self loop of even deg = even . f w/o self loop degree is odd the even + self loop of even deg = odd  .total 23 elements so if self loop there 23*2 = even degree always 

0
0
edited by

@Deepak Poonia si

@Sachin Mittal 1

any video soln ???

1
1

8 Answers

128 votes
128 votes
Best answer

Option $B$ should be the correct answer.

It is given that the number of compounds in $U = 23$ and the number of compounds in $S = 9$, so the number of compounds in $U \backslash S= 23 - 9 = 14$.


Considering each of these compounds as nodes of a graph $G$.So, vetex set of $G$ is $U$ and $S$ is a subset of vertices of $G$. 

The relation "$A$ reacts with $B$" is a symmetric relation, that is $A$ reacts with $B$ is same as $B$ reacts with $A$.

For example, consider the following reaction:

$\text{HCl + NaOH} \rightarrow \text{NaCl + H}_{2} \text{O}$

Here, we can say either $\text{HCl}$ reacts with $\text{ NaOH}$ to produce $\text{NaCl + H}_{2} \text{O}$ or we can say that $\text{ NaOH}$ reacts with $\text{HCl}$ to produce $\text{NaCl + H}_{2} \text{O}$, so both of these statements are equivalent. 

Since, the relation based on which we are going to draw the edges is symmetric, we can use an undirected edge $\left ( A, B \right )$  between any two compounds to represent the fact that $A$ reacts with $B$ as well as $B$ reacts with $A$.


Each compound in $S$ reacts with exactly $3$ compounds in $U$.

It means that the degree of every node(or compound) in $S$ is $3$.

So, sum of all the degree in $S =$ number of nodes in $S \times $ degree of each node $= 9 \times 3 = 27$.

Now in $U \backslash S$ we have $14$ nodes(or compounds), thus clearly $U \backslash S$ contains an even number of compounds.

Now if each compound in $U \backslash S$ reacts with an even number of compounds, the sum of degrees of all the node in $U \backslash S$ would be even, and consequently, the sum of degrees of all the nodes in our graph $G$ would be odd as the sum of degrees of all the nodes in $S$ is odd, and an odd number added with an even number produces an odd number.

But since in a graph, every edge corresponds to two degrees and the number of edges in a graph must be a (non-negative)integral value & not fractional value hence the sum of the degrees all the nodes of a graph must be even. (This is Handshaking Lemma).

So, statement III should be false(always).


Also, adding fourteen odd numbers gives an even number.

Hence, if each compound in $U \backslash S$ reacts with an odd number of compounds, the sum of degrees of all the node in $U \backslash S$ would be even, and consequently, the sum of degrees of all the nodes in our graph $G$ would be odd as the sum of degrees of all the nodes in $S$ is odd, and an odd number added with an even number produces an odd number.

Again by using Handshaking Lemma, this is not possible.

So, statement I should also be false(always).


Thus, from the previous two cases, it can be observed that to satisfy the Handshaking Lemma for $G$, the sum of the degrees of all the nodes $U \backslash S$ must be odd.To make this happen, we must assign at least one node of $U \backslash S$, an odd degree.

If at least, one node(or compound) in $U \backslash S$ would have an odd degree( or reacts with odd numbers of compounds) then we can assign degrees in such a way that the sum of the degrees of all the nodes $U \backslash S$ will be odd, & thus the Handshaking Lemma would be satisfied.

Hence, statement II is the only statement which is guaranteed to be true always.


Moreover, we can also make some stronger claims from the given information like,

always an odd number of compounds in $U \backslash S$ reacts with an odd number of compounds and

at least, one compound in $S$ reacts with a compound in $U \backslash S$ and so on.

edited by

4 Comments

edited by
For those who have doubt  why there is atleast one element in u/s with one element with u :

 

In u we have odd deg +_______ = 2*e

So in blank only option is odd

So in s/u will have odd deg

 

Let assume one node in s/u has deg 1  i.e odd

So other 13 elements will have even deg they only odd+even overall will be odd

Let assume those 13 elements have in b/w them even degree so then vetex which have 1 deg can't connect with those 13 elements as it will make one node degree even +1 = odd so that 1 vertex have to connect with node of S .

Now why those 13 elements has to connect in b/w because those all have even deg let say one vertex of those 13 elements connected with that one degree vetex so 1 deg vertex become odd but that vertex it is connected it has odd no of degree to connect with other because it's overall degree even , so that will connect make other vertex of those 13 odd that not possible!!! As those has to be even degree.
0
0

For 2nd statement if 2 nodes in U\S have odd degree say 3,5 and remaining 12 have even degree.So sum of degree in U\S willbe = 3+5 +12(even) will give us even degree that will be wrong.So atleast case might not work.What i am missing here.

0
0

This a Brilliant question !!
In lab set $U$ has $23$ components. Subset $S$ has $9$ compounds who will react with $3$ compounds of $U$.

$U\setminus S$ is set difference b\w $U$ and $S$. So, no. of compounds in $U\setminus S=23-9=14$

Now draw the graph acc to the condition given “$subset\;S\;of\;U\;of\;9\;compounds\;each\;of\;which\;reacts\;with\;exactly\;3\;compounds\;of\;U$”

Sum of degree of the vertice in above graph will be equal to $2\times no.\;of\;edges$

$2*(27 edges) = 9*3+(2*11)+(1*3)+(2*1)=54$

Here, we have $9$ degree=$3$ vertices (in $S$), $11$ degree-$2$ vertices & $1$ degree-$3$, $2$ degree-$1$ vertex (in $U\setminus S$)

  1. Each compound in $U \setminus S$ reacts with an odd number of compounds. $(False)$

 No, there is some compound which reacts with 2 compounds and some compounds with 1 or 3 compounds. so this is not true for each compound.

  1. At least one compound in $U \setminus S$ reacts with an odd number of compounds. $(True)$

Yes, $(3,1,1)$ these degree vertices in $U\setminus S$ reacts with odd number compounds.

  1. Each compound in $U \setminus S$ reacts with an even number of compounds. $(False)$

 Reason in I. and II.

1
1
57 votes
57 votes

The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.

Here, Set S has 9 elements and each element has a degree of 3 as each element in S  reacts to exactly 3 elements. So 9*3 + Sum. of degrees of vertices in U-S = 2* e

Since 2*e is even no, Sum of degrees of vertices in U-S is  odd .

Thus,some vertex in U-S must have odd degree. .At least one compound in U-S reacts with an odd number of compounds.

Option B is the correct answer.

edited by

3 Comments

edited by
IS 2 IS  TRUE?
0
0
Yes
0
0
simple and precise.
3
3
12 votes
12 votes
In a  undirected graph there is always even no of vertices of odd degree it's a theorem so if 9 vertices are of odd degree in 3 implies there should be at least one vertice more of odd degree

So

2 is correct
2 votes
2 votes

There are set of ‘23’ different compounds.
U = 23
∃S ∋ (S⊂U)
Each component in ‘S’ reacts with exactly ‘3’ compounds of U,

If a component ‘a’ reacts with ‘b’, then it is obvious that ‘b’ also reacts with ‘a’.
It’s a kind of symmetric relation.>br> If we connect the react able compounds, it will be an undirected graph.
The sum of degree of vertices = 9 × 3 = 27
But, in the graph of ‘23’ vertices the sum of degree of vertices should be even because
 (di = degree of vertex i.e., = no. of edges)
But ‘27’ is not an even number.
To make it an even, one odd number should be added.
So, there exists atleast one compound in U/S reacts with an odd number of compounds.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true