Question: 2014 Winter Midterm - 6

Author: Michiel Smid

Let $n \geq 7$ and $k \geq 1$ be integers, let $A$ be the set of all bitstrings of length $n$ that contain exactly seven 0s, and let $B$ be the set of all bitstrings of length $k$ that contain at least one 1. Assume there exists a one-to-one function $f : A \rightarrow B$. Which of the following is true?

(a)

$2^k - 1 < {n \choose 7}$

(b)

$2^k - 1 \geq {n \choose 7}$

(c)

$2^k - 1 \geq \left. 2^n \middle/ {n \choose n-7} \right.$

(d)

$2^k - 1 < \left. 2^n \middle/ {n \choose n-7} \right.$