Solution: 2014 Winter Midterm - 6

Author: Michiel Smid

Question

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 \geq {n \choose 7}$

(b)

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

(c)

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

(d)

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

Solution

Let A be the set of all bitstrings of length k that contain at least 1
To do this question, we can think of it as \enquote{All bitstrings minus bitstrings that have exactly 0 1's}
The only way to have exactly 0 1's is to have all 0's
Thus, the number of bitstrings that have exactly 0 1's is 1
$ |A| = 2^{k} - 1 $
Let B be the set of all bitstrings of length n that contain exactly seven 0s
We choose 7 spots out of the n spots to place the 0s
$ |B| = \binom{n}{7} $

Let’s just see what happens when $n = 7$

$ |A| = 2^{7} - 1 = 127 $

$ |B| = \binom{7}{7} = 1 $

Now, we can say for certain that $2^{n} - 1 \geq \binom{n}{7} $