Solution: 2015 Winter Final - 15

Author: Michiel Smid

Question

Let $S$ be a set of 100 integers; 30 of these are positive and the other 70 integers in $S$ are negative. We choose, uniformly at random, a 20-element subset of $S$. Let $x$ be the product of the integers in the chosen subset. What is the probability that $x > 0$?

(a)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{20} \left({70 \choose k} + {30 \choose 20 - k}\right)$

(b)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{10} \left({70 \choose 2k} + {30 \choose 20 - 2k}\right)$

(c)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{10} {70 \choose 2k}{30 \choose 20 - 2k}$

(d)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{20} {70 \choose k}{30 \choose 20 - k}$

Solution

Rephrased, it’s asking text{What are the chances that the product is positive?}

The product is positive if there are an even number of negative integers in the subset.

0 negatives and 30 positives: $ \binom{70}{0} \binom{30}{20} $

2 negatives and 28 positives: $ \binom{70}{2} \binom{30}{18} $

4 negatives and 26 positives: $ \binom{70}{4} \binom{30}{16} $

The pattern is $ \sum_{i=0}^{10} \binom{70}{2i} \binom{30}{20-2i} $

To get the probability, we need to divide by $ \binom{100}{20} $ for each case

Thus, the final answer is $ \binom{100}{20} \sum_{i=0}^{10} \binom{70}{2i} \binom{30}{20-2i} $