Solution: 2019 Fall Final - 4

Author: Michiel Smid

Question

You are given 20 beer bottles $B_1,B_2,...,B_{20}$ and 50 cider bottles $C_1,C_2,...,C_{50}$.
Consider subsets of these 70 bottles, that contain exactly 12 beer bottles (and any number of cider bottles) or exactly 12 cider bottles (and any number of beer bottles). How many such subsets are there?

(a)

${20 \choose 12} + {50 \choose 12} - {20 \choose 12} \cdot {50 \choose 12}$

(b)

${20 \choose 12} + {50 \choose 12}$

(c)

${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20} - {20 \choose 12} \cdot {50 \choose 12}$

(d)

${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20}$

Solution

Let’s do this uwu

Let A be the set of all subsets that contain exactly 12 beer bottles
We choose 12 of the 20 beer bottles: $ \binom{20}{12} $
We can have any subset of the 50 cider bottles: $ 2^{50} $
$|A| = \binom{20}{12} \cdot 2^{50} $
Let B be the set of all subsets that contain exactly 12 cider bottles
We choose 12 of the 50 cider bottles: $ \binom{50}{12} $
We can have any subset of the 20 beer bottles: $ 2^{20} $
$|B| = \binom{50}{12} \cdot 2^{20} $
Let's determine $A \cap B$
We choose 12 of the 20 beer bottles: $ \binom{20}{12} $
We choose 12 of the 50 cider bottles: $ \binom{50}{12} $
$|A \cap B| = \binom{20}{12} \cdot \binom{50}{12} $

Now, we can determine $A \cup B$

$ |A \cup B| = |A| + |B| - |A \cap B| $

$ |A \cup B| = \binom{20}{12} \cdot 2^{50} + \binom{50}{12} \cdot 2^{20} - \binom{20}{12} \cdot \binom{50}{12} $