Evaluation: 2014 Fall Midterm
1 .
Let $n \geq 2$ be an integer. How many bitstrings of length $n$ are there that contain at least two
1s?
(a)
${n \choose 2} \cdot 2^{n-2}$
(b)
$n \cdot 2^{n-1}$
(c)
$2^{n} - 1 - n$
(d)
$2^{n} - n$
2 .
How many bitstrings of length 99 are there that start with 1010 or end with 1010?
(a)
$2^{91}$
(b)
$2^{99} - 2^{96}$
(c)
$2^{95} + 2^{95}$
(d)
$2^{96} - 2^{91}$
3 .
Consider 17 boys and 17 girls. How many ways are there to arrange them on a line if all boys are
standing next to each other and all girls are standing next to each other?
(a)
$(17!)^2$
(b)
$2(17! + 17!)$
(c)
$2(17!)^2$
(d)
$17! + 17!$
4 .
Consider 12 boys, 17 girls, and 25 dogs. How many ways are there to arrange them on a line if
- all boys stand next to each other,
- all girls stand next to each other,
- all dogs stand next to each other,
- none of the boys are standing next to any of the girls.
(a)
$(12!)(17!)(25!)$
(b)
$2(12!)(17!)(25!)$
(c)
$2(12! + 17! + 25!)$
(d)
$12! + 17! + 25!$
5 .
Is the following true or false? In any group of 900 people, there must be at least three people that
have the same birthday.
(a)
False
(b)
True
6 .
Consider a square with sides of length 3. Assume this square contains 10 points. Which of the
following is true?
(a)
At least two of these $n$ points are at distance at most $\left. 1 \middle/ \sqrt{2} \right.$.
(b)
None of the above.
(c)
At least two of these $n$ points are at distance at most $1$.
(d)
At least two of these $n$ points are at distance at most $\sqrt{2}$.
7 .
What is the coefficient of $x^{20}y^{80}$ in the expansion of $(5x - 3y)^{100}$?
(a)
$-{100 \choose 80} 5^{20}3^{80}$
(b)
${80 \choose 100} 5^{20}3^{80}$
(c)
${100 \choose 80} 5^{80}3^{20}$
(d)
${100 \choose 80} 5^{20}3^{80}$
8 .
How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 27$, where $x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$, and $x_4 \geq 0$ are integers?
(a)
${30 \choose 4}$
(b)
${31 \choose 4}$
(c)
${30 \choose 3}$
(d)
${31 \choose 3}$
9 .
Let $m \geq 1$ and $n \geq 1$ be integers. Consider a rectangle whose horizontal side has length $m$
and whose vertical side has length $n$. A path from the bottom-left corner to the top-right corner is
called valid, if in each step, it either goes one unit to the right or one unit upwards.
In the example below, you see a valid path for the case when $m = 5$ and $n = 3$.
How many valid paths are there?
In the example below, you see a valid path for the case when $m = 5$ and $n = 3$.
How many valid paths are there?
(a)
${m + n \choose n}$
(b)
$2^m + 2^n$
(c)
$2^{m + n}$
(d)
${m + n \choose n - 1}$
10 .
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is defined by
$$
\begin{align}
f(0) &= 8 \\
f(n) &= f(n - 1) + 6n - 8\; \ \mathrm{for}\ n \geq 1
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = 2n^{2} - 5n + 8$
(b)
$f(n) = 2n^{2} - 5n + 7$
(c)
$f(n) = 3n^{2} - 5n + 8$
(d)
$f(n) = 4n^{2} - 5n + 8$
11 .
Let $B_n$ be the number of bitstrings of length $n$ that do not contain 1111. Which of the following
is true?
(a)
$B_n = 2^{n} - (n-3) \cdot 2^{n-4}$
(b)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(c)
$B_n = 2^{n} - 2^{n-4}$
(d)
$B_n = B_{n-1} + B_{n-2} + B_{n-3} + B_{n-4}$
12 .
$\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)
7
(b)
6
(c)
9
(d)
8
13 .
(n.b., $\log$ denotes the base-2 logarithm)
$\newcommand{\Silly}{{\rm S \scriptsize ILLY}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the following recursive algorithm $\Silly$, which takes as input an integer $n \geq 1$ which is a power of 2:
$\mathbf{Algorithm}\ \Silly(n)\mathrm{:}$
$\mathbf{if}\ n = 1$
$\mathbf{then}\ \text{drink one pint of beer}$
$\mathbf{else}\ \mathbf{if}\ n = 2$
$\elsesp \mathbf{then}\ \text{fart once}$
$\elsesp \mathbf{else}\ \text{fart once};$
$\elsesp \elsesp \Silly(n / 2);$
$\elsesp \elsesp \text{fart once}$
$\elsesp \mathbf{endif}$
$\mathbf{endif}$
(n.b., $\log$ denotes the base-2 logarithm)
(a)
$F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 2.$
(b)
$F(n) = (2 \log n) - 1\ \mathrm{for}\ n \geq 1.$
(c)
$F(n) = \log n\ \mathrm{for}\ n \geq 1.$
(d)
$F(n) = 2 \log n\ \mathrm{for}\ n \geq 1.$
14 .
You flip a fair coin 5 times. What is the probability that the first flip results in heads or the
fifth flip results in heads?
(a)
1
(b)
3/4
(c)
1/4
(d)
1/2
15 .
You flip a fair coin 5 times. Define the events
- A = "the number of heads is odd"
- B = "the number of tails is even".
(a)
$\Pr(A) = \Pr(B)$
(b)
$\Pr(A) > \Pr(B)$
(c)
$\Pr(A) < \Pr(B)$
16 .
Consider 10 boxes and 10 balls. We throw each ball, uniformly, in a random box. What is the
probability that, after we have thrown all 10 balls, none of the 10 boxes is empty?
(a)
$\frac{10^{10}}{10!}$
(b)
$1 - \frac{10 \cdot (9/10)^{10}}{10^{10}}$
(c)
None of the above.
(d)
$\frac{10!}{10^{10}}$
17 .
Assume you write a multiple-choice exam that consists of 100 questions. For each question, 4 options
are given, one of which is the correct one. If you answer each of the 100 questions by choosing an
answer uniformly at random, what is the probability that you have exactly one correct answer?
(a)
$\frac{100 \cdot 3^{99}}{4^{100}}$
(b)
$\frac{100 + 3^{99}}{4^{100}}$
(c)
$\frac{100}{4^{100}}$
(d)
$\frac{3^{99}}{4^{100}}$