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 \ S reacts with an odd number of compounds.
II. At least one compound in U \ S reacts with an odd number of compounds.
Which one of the following is ALWAYS TRUE?
A. Only I
B. Only II
C. Neither I nor II
D. Both I and II
GATE 2016 · Discrete Mathematics · Set Theory · hard
Answer: B. Only II
Total reactions involving S: Each of the 9 compounds in S reacts with exactly 3 compounds of U. The total reaction-incidence sum over S is 9 * 3 = 27.
Split into SS and S-(U\S) pairs: Each S-S reaction pair is counted twice in the sum (once for each endpoint in S), contributing 2*E_SS. Each S-(U\S) pair is counted once from the S-side, contributing E_{S,U\S}. Thus 27 = 2*E_SS + E_{S,U\S}.
Parity conclusion for U\S: The sum of (number of S-reactions for each u in U\S) equals E_{S,U\S}, which is odd. A sum of 14 numbers being odd means at least one of the 14 is odd. So Statement II is always true. Statement I (all must be odd) fails whenever two or more have the same odd contribution pattern or some are even — a valid configuration can make some even.