Solution: 2019 Fall Final - 5

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 at least 3 beer bottles (and any number of cider bottles). How many such subsets are there?

(a)

$2^{70} - 2^{50} - 20 \cdot 2^{50}$

(b)

$2^{70} - 2^{50} - 20 - {20 \choose 2}$

(c)

$2^{70} - 2^{50} - 20 \cdot 2^{50} - {20 \choose 2} \cdot 2^{50}$

(d)

None of the above.

Solution

Let S be the set of all subsets
$ |S| = 2^{70} $
Let A be the set of all subsets that contain no beer bottles
We choose 0 of the 20 beer bottles: $ \binom{20}{0} $
We choose any subset of the 50 cider bottles: $ 2^{50} $
$ |A| = \binom{20}{0} \cdot 2^{50} = 2^{50} $
Let B be the set of all subsets that contain exactly 1 beer bottle
We choose 1 of the 20 beer bottles: $ \binom{20}{1} $
We choose any subset of the 50 cider bottles: $ 2^{50} $
$ |B| = \binom{20}{1} \cdot 2^{50} = 20 \cdot 2^{50} $
Let C be the set of all subsets that contain exactly 2 beer bottles
We choose 2 of the 20 beer bottles: $ \binom{20}{2} $
We choose any subset of the 50 cider bottles: $ 2^{50} $
$ |C| = \binom{20}{2} \cdot 2^{50} = 190 \cdot 2^{50} $

Now, we can determine the number of subsets that contain at least 3 beer bottles

$ |S| - |A| - |B| - |C| $

$ = 2^{70} - 2^{50} - 20 \cdot 2^{50} -\binom{20}{2} \cdot 2^{50} $