Evaluation: 2014 Winter Midterm
1 .
On a table, you see three types of fruit: apples, bananas, and oranges. There are $m \geq 2$ apples,
$n \geq 2$ bananas, and $k \geq 2$ oranges. How many ways are there to choose 7 pieces of fruit, if
you must take at least two pieces of each type?
(a)
${m + n + k \choose 7} - {m \choose 2} - {n \choose 2} - {k \choose 2}$
(b)
${m + n + k \choose 7} - (m + n + k)$
(c)
${m \choose 2}{n \choose 2}{k \choose 2}(m + n + k)$
(d)
${m \choose 3}{n \choose 2}{k \choose 2} + {m \choose 2}{n \choose 3}{k \choose 2} + {m \choose 2}{n \choose 2}{k \choose 3}$
2 .
Consider 9 boys and 15 girls. How many ways are there to arrange these 24 people on a line if all
boys stand next to each other and all girls stand next to each other?
(a)
${24 \choose 9}(9!)(15!)$
(b)
$\frac{24!}{9!15!}$
(c)
$2(9!)(15!)$
(d)
$(9!)(15!)$
3 .
Let $S$ be a set of size 37, and let $x$, $y$, and $z$ be three distinct elements of $S$. How many subsets
of $S$ are there that contain $x$ and $y$, but do not contain $z$?
(a)
$2^{33}$
(b)
$2^{37} - 2^{35} - 2^{36}$
(c)
$2^{35}$
(d)
$2^{34}$
4 .
Let $S$ be a set of size 37, and let $x$, $y$, and $z$ be three distinct elements of $S$. How many subsets
of $S$ are there that contain $x$ or $y$, but do not contain $z$?
(a)
$2^{37} - 2^{35}$
(b)
$2^{36} - 2^{35}$
(c)
$2^{36} - 2^{34}$
(d)
$2^{37} - 2^{34}$
5 .
A password consists of 12 or 13 characters, each character being one of the 10 digits $0,1,2,\dots,9$.
A password must contain the digit 7 at least once. How many passwords are there?
(a)
$10^{12} + 10^{13} - 9^{12} - 9^{13}$
(b)
$12^{10} + 13^{10} - 12^{9} - 13^{9}$
(c)
$10^{12} + 10^{13} - 7^{12} - 7^{13}$
(d)
$12^{10} + 13^{10} - 12^{7} - 13^{7}$
6 .
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 < \left. 2^n \middle/ {n \choose n-7} \right.$
(b)
$2^k - 1 \geq \left. 2^n \middle/ {n \choose n-7} \right.$
(c)
$2^k - 1 \geq {n \choose 7}$
(d)
$2^k - 1 < {n \choose 7}$
7 .
What is the coefficient of $x^{9}y^{16}$ in the expansion of $(7x + 21y)^{25}$?
(a)
${16 \choose 25} 7^{9}21^{16}$
(b)
${25 \choose 16} 7^{25}3^{16}$
(c)
${25 \choose 16} 7^{16}21^{9}$
(d)
none of the above
8 .
How many solutions are there to the equation $x_1 + x_2 + x_3 = 17$, where $x_1 \geq 0$, $x_2 \geq 0$,
and $x_3 \geq 0$ are integers?
(a)
${19 \choose 17}$
(b)
${20 \choose 17}$
(c)
${20 \choose 16}$
(d)
${19 \choose 16}$
9 .
How many strings can be obtained by rearranging the letters of the word
POOPERSCOOPER
(a)
${13 \choose 4}{9 \choose 3}{6 \choose 2}{4 \choose 2}$
(b)
$13!$
(c)
${13 \choose 1}{12 \choose 4}{8 \choose 2}{6 \choose 1}{5 \choose 2}{3 \choose 3}$
(d)
${13 \choose 4}{9 \choose 2}{7 \choose 2}{5 \choose 3}$
10 .
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is defined by
$$
\begin{align}
f(0) &= 2 \\
f(n + 1) &= f(n) + 6n - 2\; \ \mathrm{for}\ n \geq 0
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = 2n^{2} + 5n + 2$
(b)
$f(n) = 3n^{2} - 5n + 2$
(c)
$f(n) = 3n^{2} + 5n + 2$
(d)
$f(n) = 2n^{2} - 5n + 2$
11 .
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
Consider the following recursive algorithm $\Fib$, which takes as input an
integer $n \geq 0$:
$\mathbf{Algorithm}\ \Fib(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ f = n$
$\mathbf{else}\ f = \Fib(n - 1) + \Fib(n - 2)$
$\mathbf{endif};$
$\mathbf{return}\ f$
(a)
4
(b)
6
(c)
5
(d)
7
12 .
The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for
$n \geq 2$.
Consider again the recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:
Which of the following is true?
Consider again the recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:
$\mathbf{Algorithm}\ \Fib(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ f = n$
$\mathbf{else}\ f = \Fib(n - 1) + \Fib(n - 2)$
$\mathbf{endif};$
$\mathbf{return}\ f$
Which of the following is true?
(a)
For $n \geq 3$, $a_n = f_{n - 1}$
(b)
For $n \geq 3$, $a_n = f_{n + 1}$
(c)
For $n \geq 3$, $a_n = -1 + f_n$
(d)
For $n \geq 3$, $a_n = f_n$
13 .
Let $B_n$ be the number of bitstrings of length $n$ that do not contain 111. Which of the following
is true?
(a)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(b)
$B_n = B_{n-1} + B_{n-2} + 2^{n-3} - B_{n-3}$
(c)
$B_n = B_{n-1} + B_{n-2} + 2^{n-3}$
(d)
$B_n = B_{n-1} + B_{n-2} + B_{n-3} + 2^{n-4}$
14 .
A standard deck of 52 cards has 4 Kings. Consider a hand of 9 cards, chosen uniformly at random.
What is the probability that there are exactly two Kings in this hand?
(a)
$\left. \bigl\{ {4 \choose 2} + {48 \choose 7} \bigr\} \middle/ {52 \choose 9} \right.$
(b)
$\left. {4 \choose 2}{48 \choose 7} \middle/ {52 \choose 9} \right.$
(c)
$\left. {52 \choose 9} \middle/ \bigl\{ {4 \choose 2}{48 \choose 7} \bigr\} \right.$
(d)
$1 - \left. {48 \choose 7} \middle/ {52 \choose 9} \right.$
15 .
We choose a bitstring of length 25 uniformly at random. What is the probability that this string
contains at least two 1s?
(a)
$1 - (1/2)^{25} - 25(1/2)^{25}$
(b)
none of the above
(c)
$\sum_{k=2}^{25} {{25}\choose{k}}(1/2)^{k}$
(d)
$1 + (1/2)^{25} - 25(1/2)^{25}$
16 .
Consider three people, each one having a uniformly random birthday (out of 365 days; we ignore leap
years). What is the probability that at least two of them have the same birthday?
(a)
$1 - \left. {3 \choose 2} \middle/ 365^3 \right.$
(b)
$1 - \frac{365^2}{364 \cdot 363}$
(c)
$1 - \frac{364 \cdot 363}{365^2}$
(d)
$1 - \left. \bigl\{ {3\choose 2} + {3 \choose 3} \bigr\} \middle/ 365^3 \right.$