edited by
16,415 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.
edited by

8 Answers

0 votes
0 votes
Kindly someone tell me if it's wrong, bcs everyone is using graph theory and all.

U-S has 14 elements.

The 9 elements of S, each of them take 3 elements from 14 elements of U-S.

So after 4th element of S, we have weared out 3*4 = 12 elements of U-S.

Remaining 5 elements of S needs 15 elements of U-S, so it comes full circle covering the remaining 2 elements as well as 13 elements a second time. Leaving one element, which was taken only once.

So there is one element which is taken only once. So one element with odd no of elements reacting with it is there always.
0 votes
0 votes
Can i apply pigeon hole principle here?

u/s=14.

And if first 9 compound of (u/s) react with 9 compound of S,then I have only 5 compound left which will react 5 compound of S.

Now in (u/s) some compound reacts with 2 compounds and some compound reacts with only 1 compound.

So in (u/s) has some elements which react with odd no of elements of S.
0 votes
0 votes

We shall use graph theory to answer this question. Let $G$ be an undirected graph. Assume a vertex for each compound. Also there is an edge between two vertices if and only if the two compounds react. As an example case suppose that all the elements in $S$ react with only elements in $S$. So in the induced subgraph corresponding the vertices in $S$, each vertex has odd degree and there are $9$ vertices in $S$. So we have odd no. of vertices of odd degree which is not possible. So the tightest example which we can have is as shown:

If the situation is as given and let us assume that the vertices in $U\backslash S$ which are not shown ($11$ such vertices are there) do not react with anything, then we reach at contradiction of :

Statement 1 : Because, here in the above example the $11 (=  23-9\text{(vertices of S)}-3\text{(vertices in blue)}$ vertices have even degree. So every vertices does not have odd degree.

Statement 3: Because, here in the above example, the $3$ blue vertices have odd degree [$1$ as shown]. So every vertex does not have even degree.

What about statement 2? In this example statement 2 is correct. Why? Let us assume that statement 2 is false. So all the $14$ vertices of $U\backslash S$ should have even degrees in graph $G$. But in $G-S$ the three blue vertices should have odd degrees, which is not possible, as a graph should have an even no of vertices with odd degrees.

But we cannot say about the correctness of a statement, just by proving it correct for one example case. We need to show that it is true for all cases. So again let us assume that statement 2 is false. So all the $14$ vertices of $U\backslash S$ should have even degrees in graph $G$. So their degree sum is also even. Also the $9$ vertices in $S$ have degree $3$ each. So sum their degree sum is $9* 3=27$ which is odd. So sum of degrees of the vertices of the graph = even+odd= an odd number. But degree sum of the vertices of a graph graph is twice the number of edges in the graph and hence even. So we arrive at a contradiction and statement 2 is true indeed. [This proof actually also proves that statement 3 is false].


A formal proof that statement 1 is wrong: if all $14$ vertices in $U\backslash S$ have odd degree then their degree sum shall be odd. Also we know degree sum of the vertices in $S$ is odd, so the degree sum of the vertices in $G$ shall be odd which is not possible,

0 votes
0 votes

 

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

according to question

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 9x3 + 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.

So Option B is the correct answer.

Answer:

Related questions