Solution: 2017 Fall Midterm - 4

Author: Michiel Smid

Question

Let $m \geq 5$ and $n \geq 5$ be integers. Let $P$ be a set consisting of $m$ strictly positive integers, and let $N$ be a set consisting of $n$ strictly negative integers. Consider 5-element subsets $A$ of $P \cup N$ such that the product of the elements in $A$ is strictly positive. How many such subsets $A$ are there?

(a)

${n \choose 5} + {n \choose 3} \cdot {m \choose 2} + n \cdot {m \choose 4}$

(b)

${m+n \choose 5} - {n \choose 5}$

(c)

${m \choose 5} + {m \choose 3} \cdot {n \choose 2} + m \cdot {n \choose 4}$

(d)

${m \choose 5} \cdot {n \choose 5}$

Solution

If we want the product to be positive, there are only 3 possibilities:

5 positive numbers

We choose 5 positive numbers from $ m $ positive numbers: $ \binom{m}{5} $
3 positive numbers and 2 negative numbers

We choose 3 positive numbers from $ m $ positive numbers and 2 negative numbers from $ n $ negative numbers: $ \binom{m}{3} \cdot \binom{n}{2} $
1 positive number and 4 negative numbers

We choose 1 positive number from $ m $ positive numbers and 4 negative numbers from $ n $ negative numbers: $ m \cdot \binom{n}{4} $

Thus, there are $ \binom{m}{5} + \binom{m}{3} \cdot \binom{n}{2} + m \cdot \binom{n}{4} $ such subsets.