Evaluation: 2017 Winter Midterm
1 .
Carleton's Computer Science program has $f$ female students and $m$ male students, where $f \geq 1$
and $f + m \geq 8$. The Carleton Computer Science Society has a Board of Directors consisting of a
President, five Vice-Presidents, and two Cider-Presidents (whose task is to buy cider for the
President). All members of the Board of Directors are Computer Science students. The President is
female, cannot be Vice-President, and cannot be Cider-President. A Vice-President cannot be Cider-President.
In how many ways can a Board of Directors be chosen?
(a)
$f \cdot {f+m-1 \choose 7}$
(b)
$f \cdot {f+m-1 \choose 5} \cdot {f+m-6 \choose 2}$
(c)
$f \cdot {f+m \choose 5} \cdot {f+m \choose 2}$
(d)
$f + {f+m-1 \choose 5} + {f+m-6 \choose 2}$
2 .
Let $b \geq 1$ and $g \geq 1$ be integers. Consider $b$ boys and $g$ girls. How many ways are there
to arrange these kids on a line such that the leftmost kid is a girl?
(a)
$(b + g)! / b$
(b)
None of the above.
(c)
$g \cdot (b + g - 1)!$
(d)
$(b + g)!$
3 .
Let $b \geq 1$ and $g \geq 1$ be integers. Consider $b$ boys and $g$ girls. How many ways are there
to arrange these kids on a line such that the leftmost kid is a girl or the rightmost kid is a boy?
(a)
$(b+g)! - b \cdot (b+g-1)! -\ $ $ g \cdot (b+g-1)!$
(b)
$g \cdot (b+g-1)! + b \cdot (b+g-1)!\ -$ $ b \cdot g \cdot (b+g-2)!$
(c)
$g \cdot (b+g-1)! + b \cdot (b+g-1)!\ -$ $ b \cdot g \cdot (b+g-1)!$
(d)
$(b+g)!$
4 .
Let $n \geq 13$ be an integer. What is the number of bitstrings of length $n$ that have exactly
seven 0's or exactly five 1's?
(a)
${n \choose 7} + {n \choose 5}$
(b)
${n \choose 12} \cdot {12 \choose 7}$
(c)
${n \choose 7} + {n \choose 5} - {n \choose 5} \cdot {n - 5 \choose 7}$
(d)
None of the above.
5 .
Consider strings of length six consisting of the characters $a$, $b$, $c$, and $d$. How many such
strings are there that start with $abc$ or end with $cccc$?
(a)
81
(b)
82
(c)
80
(d)
79
6 .
Let $n \geq 4$ be an integer and consider strings of length $n$ consisting of the characters $a$, $b$,
$c$, and $d$. How many such strings are there that start with $ab$ or start with $abc$?
(a)
$4^{n-1}$
(b)
$4^{n}$
(c)
$4^{n-2}$
(d)
$4^{n-3}$
7 .
Let $m \geq 2$ and $n \geq 2$ be integers. What does
$$
{m \choose 2} + {n \choose 2} + mn
$$
count?
(a)
The number of ways to choose an ordered pair $(x,y)$ from a group consisting of $m$ men and $n$ women, where $x$ and $y$ cannot both be men.
(b)
The number of ways to choose an unordered pair of people from a group consisting of $m$ men and $n$ women.
(c)
The number of ways to choose an ordered pair $(x,y)$ from a group consisting of $m$ men and $n$ women, where $x$ must be a man and $y$ must be a woman.
(d)
The number of ways to choose an unordered pair of people from a group consisting of $m$ men and $n$ women, where at least one man must be chosen.
8 .
Each student has a student number which is a string of five digits, in which no digit occurs more
than once. Thus, 94631 is a valid student number, whereas 94641 is not valid.
What is the minimum number of students such that we can guarantee that at least two of them have the same student number?
What is the minimum number of students such that we can guarantee that at least two of them have the same student number?
(a)
$1 + 10^{5}$
(b)
$1 + \frac{10!}{5!}$
(c)
$1 + 5^{10}$
(d)
$1 + \frac{5!}{10!}$
9 .
What is the coefficient of $x^{20}y^{80}$ in the expansion of $(7x-13y)^{100}$?
(a)
${100 \choose 80} \cdot 7^{20} \cdot 13^{80}$
(b)
$- {100 \choose 80} \cdot 7^{20} \cdot 13^{80}$
(c)
${100 \choose 20} \cdot 7^{80} \cdot 13^{20}$
(d)
$- {100 \choose 20} \cdot 7^{80} \cdot 13^{20}$
10 .
How many strings can be obtained by rearranging the letters of the word
POOPERSCOOPER
(a)
${13 \choose 4}{13 \choose 3}{13 \choose 2}{13 \choose 2}{13 \choose 1}$
(b)
$13!$
(c)
${13 \choose 4}{9 \choose 3}{6 \choose 2}{4 \choose 2}{2 \choose 1}$
(d)
${13 \choose 4}{9 \choose 3}{6 \choose 2}{4 \choose 2}$
11 .
A bitstring is called 00-free if it does not contain two 0's next to each other.
In class, we have seen that for any $m \geq 1$,
the number of 00-free bitstrings of length $m$ is equal to the $(m+2)$-th Fibonacci number $f_{m+2}$.
Let $n \geq 3$ be an integer. What is the number of 00-free bitstrings of length $3n-1$ that have 0 at position $n$ and 1 at position $2n$? (The positions are numbered $1,2,\dots,3n-1)$.
(n.b., $f^2_x = f_x \cdot f_x$)
Let $n \geq 3$ be an integer. What is the number of 00-free bitstrings of length $3n-1$ that have 0 at position $n$ and 1 at position $2n$? (The positions are numbered $1,2,\dots,3n-1)$.
(n.b., $f^2_x = f_x \cdot f_x$)
(a)
${f^2_{n}} \cdot f_{n+1}$
(b)
${f^2_{n+1}} \cdot f_{n+2}$
(c)
${f^2_{n+2}} \cdot f_{n+1}$
(d)
${f^2_{n+1}} \cdot f_n$
12 .
The function $f : \{1,2,3,\dots\} \rightarrow \mathbb{R}$ is defined by
$$
\begin{align}
f(1) &= 2, \\
f(n) &= 2 \left( \frac{n - 1}{n} \right)^2 \cdot f(n - 1)\ \mathrm{if}\ n \geq 2.
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = \frac{2^{n-1}}{n^{2}}$
(b)
$f(n) = \frac{2^{n}}{n^{2}}$
(c)
$f(n) = \frac{2^{n}}{(n-1)^{2}}$
(d)
$f(n) = \frac{n^{2}}{2^{n}}$
13 .
For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain
the substring 10. Which of the following is true for any $n \geq 4$?
(a)
$B_n = f_{n+2}$, the $(n+2)$-nd Fibonacci number.
(b)
$B_n = n+1$
(c)
$B_n = n$
(d)
$B_n = f_{n+1}$, the $(n+1)$-st Fibonacci number.
14 .
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 3's and 4's, such that the order in which the 3's and 4's occur in the sum matters.
For example, $S_5 = 0$, because 5 cannot be written as a sum of 3's and 4's.
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 - 1} + S_{n - 2}$
(b)
$S_n = S_{n - 2} + S_{n - 3}$
(c)
$S_n = S_{n - 3} + S_{n - 4}$
(d)
$S_n = 2 \cdot S_{n - 1}$
15 .
$\newcommand{\Hello}{{\rm H {\scriptsize ELLO}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the recursive algorithm $\Hello$, which takes as input an integer $n \geq 0$:
(see document for missing code)
If we run algorithm $\Hello(7)$, how many times is the word "hello" printed?
(a)
4
(b)
5
(c)
7
(d)
6
16 .
You flip a fair coin 15 times. Define the event
- A = "the result of the first three flips are equal".
(a)
1/2
(b)
1/4
(c)
1/6
(d)
1/8
17 .
Let $n \geq 1$ be an integer. A bag contains $n$ red balls and $n$ blue balls. We choose a uniformly
random subset of two balls. Define the event
- A = "this subset consists of one red ball and one blue ball".
(a)
$\left. {2n \choose 2} \middle/ n^2 \right.$
(b)
$\left. {n \choose 2} \middle/ n^2 \right.$
(c)
$\left. n^2 \middle/ {2n \choose 2} \right.$
(d)
$\left. n^2 \middle/ {n \choose 2} \right.$