how to solve this question using set theory?

Question

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!

Answer 1

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.

Answer 2

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.