Consider a set \(U\) of 23 different compounds in a Chemistry lab. There is a…
2016
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:
I. Each compound in \(U \setminus S
\) reacts with an odd number of compounds.
II. At least one compound in \(U \setminus S
\) reacts with an odd number of compounds.
III. Each compound in \(U \setminus 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
Attempted by 123 students.
Show answer & explanation
Correct answer: B
Key idea: model the compounds as vertices of a graph and reactions as edges; use parity of degree sums.
Each compound in S has degree 3, so the total degree contributed by S is 9 × 3 = 27 (odd).
The total sum of degrees of all vertices equals twice the number of reactions, so it is even.
Therefore the sum of degrees of the 14 vertices in U \ S is even − 27 = odd, which forces at least one of those 14 degrees to be odd.
Conclusion: At least one compound in U \ S reacts with an odd number of compounds, so the statement 'At least one compound in U \ S reacts with an odd number of compounds' is always true. The other statements are not guaranteed by this parity argument.