0
$\begingroup$

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?

A. Only I

B. Only II

C. Only III

D. None

==============================================================

Answer given in book is- 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.

But How to solve it using set theory? Also, is there any other way solve this question!

$\endgroup$
  • 1
    $\begingroup$ No. There is no other way to solve this question. You can phrase the solution in a way that doesn't say the word "vertex" or "degree", but it will still be the same solution. $\endgroup$ – Misha Lavrov Oct 25 '18 at 14:58
  • $\begingroup$ Also: What do you mean by "solve it using set theory"? Pretty much every current day proof is a set theoretic proof in one way or another... And that's not a coincidence. Set theory, from the beginning, was designed to encompass all(*) of mathematics. $\endgroup$ – Stefan Mesken Oct 25 '18 at 15:07
  • $\begingroup$ @Stefan Mesken The solution given in book uses, THE CONCEPT OF graph theory but I specifically asked, how to solve it using set theory, as I am at BEGINNER level and didn't knew that "Set theory, from the beginning, was designed to encompass all(*) of mathematics." No one taught me that in my DISCRETE MATHEMATICS COURSE. Also, please tell if the below answer posted is correct or not? $\endgroup$ – Geeklovenerds Oct 26 '18 at 4:13
1
$\begingroup$

Here is a restatement of the book solution which does not use graph theory. For shorthand, let's call a compound "even" if it reacts with an even number of compounds, and "odd" if reacts with an odd number of compounds.

Since each compound of $S$ reacts with exactly $3$ compounds of $U$, there are a total of $27$ reactions between $U$ and $S$. Distributing those $27$ reactions between the $13$ compounds in $U \setminus S$ can be done in many ways, but we know that it's impossible for all $13$ compounds in $U \setminus S$ to be even, because then the total number of reactions would be even, but $27$ is odd.

In fact, no matter how we distribute the reactions, the number of odd compounds in $U \setminus S$ is odd, because the total must be odd. (If we add up $k$ odd numbers, and $13-k$ even numbers, then the total is odd when $k$ is odd, and even when $k$ is even.)

So far, it seems that statement II is true. But we haven't yet considered reactions between two compounds in $U \setminus S$.

It turns out that this doesn't make a difference. There are three cases:

  • If we add a reaction between an even compound and an odd compound, then the even compound becomes odd and the odd compound becomes even, but the number of odd compounds doesn't change.
  • If we add a reaction between two even compounds, they both become odd. So there is still an odd number of odd compounds in $U \setminus S$ (their number has gone up by $2$, so it stays odd).
  • If we add a reaction between two odd compounds, they both become even. So there is still an odd number of odd compounds in $U \setminus S$ (their number has gone down by $2$, so it stays odd).

As a result, no matter how many reactions between compounds in $U \setminus S$ there are, one compound in $U \setminus S$ will still be odd, proving statement II.

$\endgroup$
-1
$\begingroup$

Consider all compounds as numbers like {1,2,,.....,23} and let’s consider subset S={1,2,.,8,9}.

Now if we assign 3 compound of U\S to each element of set S in such a way that.

1: 10,11,12

2: 13,14,15

3: 16,17,18

4: 19,20,21

5: 22,23,10 (here you can see we have to start again from 10 as we have only 10-23
compounds with us)

6: 11,12,13 7: 14,15,16

8: 17,18,19

9: 20,21,22

Now you can see from above assignments that 10-22 reacts with even no. of compounds but 23 reacts with odd number of compounds.

So option (B) is the right one.

Note: There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. If you consider that all S elements reacts with itself too..then in that case 3 elements in U\S react with 1 (odd) element of S .

please let me know if anything wrong with this method.

$\endgroup$
  • $\begingroup$ You have found one specific way to pick which compounds react with which other compounds. It disproves statements I and III, because a single counterexample is enough to disprove a claim that something is always true. It doesn't prove statement II, because maybe there is some other way to pick which compounds react together, for which statement II is false. $\endgroup$ – Misha Lavrov Oct 26 '18 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.