# how to solve this question using set theory?

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!

• 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. – Misha Lavrov Oct 25 '18 at 14:58
• 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. – Stefan Mesken Oct 25 '18 at 15:07
• @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? – Geeklovenerds Oct 26 '18 at 4:13

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.

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.

• 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. – Misha Lavrov Oct 26 '18 at 5:18