Solution: 2018 Winter Midterm - 8

Author: Michiel Smid

Question

Let $m \geq 34$ be an even integer, let $n \geq 1$ be an integer, and consider the two sets $$ A = \{1,2,\dots,m\} $$ and $$ B = \{m+1,m+2,\dots,m+n\}. $$ Let $k$ be an integer with $17 \leq k \leq n+17$.
Consider subsets $X$ of $A \cup B$, such that $|X| = k, |X \cap A| = 17$, and all elements of $X \cap A$ are even.
How many such subsets $X$ are there?

(a)

${m/2 \choose 17} \cdot {n \choose k-17}$

(b)

${m \choose 17} \cdot {n \choose k-17}$

(c)

${m+n \choose 17} \cdot {n \choose k-17}$

(d)

${m/2+n \choose 17} \cdot {n \choose k-17}$

Solution

There are no elements that are in both $ A $ and $ B $.

Because $ | X \cap A | = 17 $, we know 17 elements are from $ A $.

Because all elements of $ X \cap A $ are even, we know 17 of the elements from $ A $ are all even.

Because of this, we can only use half of the elements from $ A $ to fill the 17 even elements: $ \frac{m}{2} $

We choose 17 elements from half of $ A $: $ \binom{m/2}{17} $

The remaining $ k-17 $ elements must come from $ B $: $ \binom{n}{k-17} $

Thus, there are $ \binom{m/2}{17} \cdot \binom{n}{k-17} $ such subsets.