Evaluation: 2016 Fall Midterm
1 .
Carleton's Computer Science program has $f$ female students and $m$ male students, where
$f \geq 1$ and $f + m \geq 4$. The Carleton Computer Science Society has a Board of Directors
consisting of a President and three Vice-Presidents, all of whom are Computer Science students.
The President is female and cannot be a Vice-President. In how many ways can a Board of Directors
be chosen?
(a)
$f \cdot {f + m - 1 \choose 3}$
(b)
$(f - 1) \cdot {f + m \choose 3}$
(c)
$f \cdot {f + m \choose 3}$
(d)
${f + m \choose 4}$
2 .
Let $k$ and $n$ be integers with $2 \leq k \leq n$ and consider the set $S = \{1,2,\dots,n\}$.
What is the number of $k$-element subsets of $S$ that do not contain 1 and do not contain 2?
(a)
${n - 1 \choose k}$
(b)
${n - 1 \choose k - 1}$
(c)
${n - 2 \choose k - 2}$
(d)
${n - 2 \choose k}$
3 .
Let $k$ and $n$ be integers with $2 \leq k \leq n$ and consider the set $S = \{1,2,\dots,n\}$.
What is the number of $k$-element subsets of $S$ that do not contain 1 or do not contain 2?
(a)
${n - 1 \choose k} + {n - 1 \choose k}$
(b)
${n \choose k} - {n - 1 \choose k - 1} - {n - 1 \choose k - 1}$
(c)
${n \choose k} - {n - 2 \choose k - 2}$
(d)
${n - 2 \choose k}$
4 .
For any integer $n \geq 3$, let $B_n$ be the number of bitstrings of length $n$ in which the first
three bits are not all equal. Which of the following is true?
(a)
$B_n = 2^n - 6$
(b)
$B_n = 2^n - 2$
(c)
$B_n = 6 \cdot 2^{n - 3}$
(d)
$B_n = 2 \cdot 2^{n - 3}$
5 .
Consider strings of length 4 consisting of the characters $a$, $b$, $c$, and $d$.
How many such strings are there that start with $ad$ or end with $dcb$?
(a)
18
(b)
19
(c)
20
(d)
17
6 .
Let $n \geq 5$ and consider strings of length $n$ consisting of the characters $a$, $b$, $c$, and $d$.
How many such strings are there that start with $ad$ or end with $dcb$?
(a)
$4^n - 4^{n - 5}$
(b)
$4^{n - 2} + 4^{n - 3}$
(c)
$4^{n - 2} + 4^{n - 3} - 4^{n - 5}$
(d)
$4^n - 4^{n - 2} - 4^{n - 3}$
7 .
What does
$$
{w \choose 3} \cdot {m \choose 2} + {w \choose 4} \cdot m + {w \choose 5}
$$
count?
(a)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men,
where at least 3 women must be chosen.
(b)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men,
where at most 3 women can be chosen.
(c)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men,
where at most 3 men can be chosen.
(d)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men,
where at least 3 men must be chosen.
8 .
Let $n \geq 2$ be an integer and let $S$ be a set of $m$ integers. What is the minimum value
of $m$ such that we can guarantee that $S$ contains at least two elements whose difference
is divisible by $n$?
(a)
$n + 1$
(b)
$n + 2$
(c)
$n - 1$
(d)
$n$
9 .
What is the coefficient of $x^{24}y^{26}$ in the expansion of $(5x - 7y)^{50}$?
(a)
${50 \choose 24} \cdot 5^{26} \cdot 7^{24}$
(b)
${50 \choose 26} \cdot 5^{24} \cdot 7^{26}$
(c)
$- {50 \choose 24} \cdot 5^{26} \cdot 7^{24}$
(d)
$- {50 \choose 26} \cdot 5^{24} \cdot 7^{26}$
10 .
The function $f : \mathbb{N} \rightarrow \mathbb{R}$ is defined by
$$
\begin{align}
f(0) &= 7, \\
f(n) &= \frac{n}{3} \cdot f(n - 1)\; \ \mathrm{for}\ n \geq 1.
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = 7^n \cdot \frac{(n + 1)!}{3^n}$
(b)
$f(n) = 7^n \cdot \frac{n!}{3^n}$
(c)
$f(n) = 7 \cdot \frac{n!}{3^n}$
(d)
$f(n) = 7 \cdot \frac{(n + 1)!}{3^n}$
11 .
For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not
contain the substring 11 and do not contain the substring 101. Which of the following is true
for any $n \geq 4$?
(a)
$B_n = B_{n - 2} + B_{n - 4}$
(b)
$B_n = B_{n - 1} + B_{n - 2}$
(c)
$B_n = B_{n - 2} + B_{n - 3}$
(d)
$B_n = B_{n - 1} + B_{n - 3}$
12 .
Let $n \geq 1$ be an integer, and let $S_n$ be the number of ways in which $n$ can be written
as a sum of 3s and 4s, such that the order in which the 3s and 4s occur in the sum matters.
For example, $S_5 = 0$, because 5 cannot be written as a sum of 3s and 4s.
We have $S_{11} = 3$, because
Which of the following is true for any $n \geq 5$?
| $11$ | $= 3 + 4 + 4 = 4 + 3 + 4$ $= 4 + 4 + 3.$ |
(a)
$S_n = S_{n - 2} + S_{n - 3}$
(b)
$S_n = 2 \cdot S_{n - 1}$
(c)
$S_n = S_{n - 1} + S_{n - 2}$
(d)
$S_n = S_{n - 3} + S_{n - 4}$
13 .
$\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)
5
(c)
6
(d)
7
14 .
(n.b., $\log$ denotes the base-2 logarithm)
$\newcommand{\ElisaDrinksCider}{{\rm E {\scriptsize LISA} D {\scriptsize RINKS} C {\scriptsize IDER}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the following recursive algorithm $\ElisaDrinksCider$, which takes as input an integer
$n \geq 1$, which is a power of 2:
$\mathbf{Algorithm} \text{ ElisaDrinksCider}(n):$
$\quad \mathbf{if}\ n = 1\ \mathbf{then}$
$\quad \quad \text{order Fibonachos}$
$\quad \mathbf{else}$
$\quad \quad \ElisaDrinksCider(n / 2);$
$\quad \quad \text{drink n bottles of cider};$
$\quad \quad \ElisaDrinksCider(n / 2)$
$\quad \mathbf{endif}$
(n.b., $\log$ denotes the base-2 logarithm)
(a)
$C(n) = 2n \log n$
(b)
$C(n) = n \log n + 1$
(c)
$C(n) = n \log n$
(d)
$C(n) = n \log n - 1$
15 .
You flip a fair coin 9 times. Define the event
- A = "the result of the first flip is not equal to the result of the second flip".
(a)
1
(b)
1/2
(c)
1/4
(d)
1/3
16 .
Consider 4 people, each of which has a uniformly random birthday. We ignore leap years; thus, one year
has 365 days. Define the event
- A = "at least 2 of these 4 people have the same birthday".
(a)
$1 - \frac{362 \cdot 363 \cdot 364}{365^3}$
(b)
${4 \choose 2} \cdot \frac{1}{365} + {4 \choose 3} \cdot \frac{1}{365^2} + {4 \choose 4} \cdot \frac{1}{365^3}$
(c)
${4 \choose 2} \cdot \frac{1}{365}$
(d)
$1 - \frac{361 \cdot 362 \cdot 363 \cdot 364}{365^4}$