Evaluation: 2017 Fall Midterm
1 .
Let $n \geq 8$ be an even integer and let $S = \{1,2,3,\dots,n\}$. Consider 7-element subsets of $S$
that consist of 4 even numbers and 3 odd numbers. How many such subsets are there?
(a)
${n \choose 4} + {n \choose 3}$
(b)
${n \choose 4} \cdot {n \choose 3}$
(c)
${n/2 \choose 4} + {n/2 \choose 3}$
(d)
${n/2 \choose 4} \cdot {n/2 \choose 3}$
2 .
Let $s \geq 1$, $t \geq 1$, and $k \geq 1$ be integers. The Carleton Computer Science Society is
organizing their annual Halloween party. At this party, there are
- $s$ students who are dressed up as Superman,
- $t$ students who are dressed up as Donald Trump,
- $k$ students who are dressed up as Kim Jong Un.
(a)
$2 \cdot s! \cdot t! \cdot k!$
(b)
$s! \cdot t! \cdot k!$
(c)
$\left. (s+t+k)! \middle/ (2 \cdot s! \cdot t! \cdot k!) \right.$
(d)
$\left. (s+t+k)! \middle/ (s! \cdot t! \cdot k!) \right.$
3 .
Let $n \geq 1$ be an integer. Consider functions
$$
f : \{1,2,3,\dots,n\} \rightarrow \{1,2,3,\dots,7n\}
$$
such that, for each $i$ with $1 \leq i \leq n$, $f(i)$ is divisible by 7. How many such functions
are there?
(a)
$7^{n}$
(b)
$n^{7n}$
(c)
$n^{n}$
(d)
$(7n)^{n}$
4 .
Let $m \geq 5$ and $n \geq 5$ be integers. Let $P$ be a set consisting of $m$ strictly positive
integers, and let $N$ be a set consisting of $n$ strictly negative integers. Consider 5-element
subsets $A$ of $P \cup N$ such that the product of the elements in $A$ is strictly positive. How
many such subsets $A$ are there?
(a)
${n \choose 5} + {n \choose 3} \cdot {m \choose 2} + n \cdot {m \choose 4}$
(b)
${m+n \choose 5} - {n \choose 5}$
(c)
${m \choose 5} + {m \choose 3} \cdot {n \choose 2} + m \cdot {n \choose 4}$
(d)
${m \choose 5} \cdot {n \choose 5}$
5 .
Let $n \geq 2$ be an even integer and let $S = \{1,2,3,\dots,n\}$. Consider subsets of $S$ that
contain at least one even number. How many such subsets are there?
(a)
$2^{n/2} + 2^{n/2}$
(b)
$2^{n} + 2^{n/2}$
(c)
$2^{n} - 2^{n/2}$
(d)
$(n/2) \cdot 2^{n/2}$
6 .
Let $n \geq 7$ 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 $abc$ or end with $dddd$?
(a)
$4^{n-3} + 4^{n-4} - 4^{n-7}$
(b)
$2 \cdot 4^{n-4} - 4^{n-7}$
(c)
$2 \cdot 4^{n-3} - 4^{n-7}$
(d)
$4^{n-3} + 4^{n-4}$
7 .
Let $n \geq 2$ be an integer. What does
$$
\sum_{k=2}^{n} {{n}\choose{k}} \cdot 2^{n-k}
$$
count?
(a)
The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least 2 many $a$'s.
(b)
The number of strings of length $n$, where each character is $a$ or $b$, that contain at least one $a$.
(c)
The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least one $a$.
(d)
The number of strings of length $n$, where each character is $a$ or $b$, that contain at least 2 many $a$'s.
8 .
Consider a square with sides of length 17. This square contains $n$ points. What is the minimum
value of $n$ such that we can guarantee that at least two of these points have distance at most
$\left. 17 \middle/ \sqrt{2} \right.$?
(a)
5
(b)
7
(c)
4
(d)
6
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 20} \cdot 7^{80} \cdot 13^{20}$
(c)
${100 \choose 80} \cdot 7^{20} \cdot 13^{80}$
(d)
$- {100 \choose 20} \cdot 7^{80} \cdot 13^{20}$
10 .
A bitstring is called 01-free if it does not contain 01.
Let $n \geq 2$ be an integer. How many 01-free bitstrings of length $n$ are there?
(a)
$n-1$
(b)
$n+1$
(c)
$n+2$
(d)
$n$
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}$.
What is the number of 00-free bitstrings of length 20 that have 0 at position 7? (The positions are numbered $1,2,\dots,20$.)
What is the number of 00-free bitstrings of length 20 that have 0 at position 7? (The positions are numbered $1,2,\dots,20$.)
(a)
$f_{7} \cdot f_{15}$
(b)
$f_{8} \cdot f_{14}$
(c)
$f_{7} \cdot f_{14}$
(d)
$f_{8} \cdot f_{15}$
12 .
The functions $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ and $g : \mathbb{N} \rightarrow \mathbb{N}$
are recursively defined as follows:
For any integer $n \geq 0$, what is $f(g(n), g(n))$?
| $f(m, 0)$ | $= m\ \;$ | $\mathrm{if}\ m \geq 0,$ |
| $f(m, n)$ | $= 1 + f(m, n - 1)\ \;$ | $\mathrm{if}\ m \geq 0$ $\mathrm{and}\ n \geq 1,$ |
| $g(0)$ | $= 1,$ | |
| $g(n)$ | $= 5 \cdot g(n - 1)\ \;$ | $\mathrm{if}\ n \geq 1.$ |
(a)
$2 \cdot 5^{n-1}$
(b)
$(5^{n})^{2}$
(c)
$2 \cdot 5^{n}$
(d)
$(5^{n-1})^{2}$
13 .
Consider strings of characters, where each character is $a$, $b$, or $c$. Such a string is called ccc-free
if it does not contain ccc.
For any integer $n \geq 4$, let $B_n$ be the number of ccc-free strings of length $n$. Which of the following is true?
For any integer $n \geq 4$, let $B_n$ be the number of ccc-free strings of length $n$. Which of the following is true?
(a)
$B_n = B_{n-1} + B_{n-2} + 2 \cdot B_{n-3}$
(b)
$B_n = 2 \cdot B_{n-1} + 2 \cdot B_{n-2} + 2 \cdot B_{n-3}$
(c)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(d)
$B_n = 2 \cdot B_{n-1} + 2 \cdot B_{n-2} + B_{n-3}$
14 .
Let $n \geq 1$ be an integer and consider a $2 \times n$ board $B_n$ consisting of a total of $2n$ square cells.
The top part of the figure below shows $B_{13}$.
A brick is a horizontal or vertical board consisting of 2 square cells; see the bottom part of the figure
above. A tiling of the board $B_n$ is a placement of bricks on the board such that
Let $T_n$ be the number of different tilings of the board $B_n$. Which of the following is true for any $n \geq 3$?
A brick is a horizontal or vertical board consisting of 2 square cells; see the bottom part of the figure
above. A tiling of the board $B_n$ is a placement of bricks on the board such that
- the bricks exactly cover $B_n$ and
- no two bricks overlap.
Let $T_n$ be the number of different tilings of the board $B_n$. Which of the following is true for any $n \geq 3$?
(a)
$T_n = T_{n + 1} + T_{n + 2}$
(b)
$T_n = T_{n - 1} + T_{n - 2}$
(c)
$T_n = T_{n - 1} + 2 \cdot T_{n - 2}$
(d)
$T_n = 2 \cdot T_{n - 1} + T_{n - 2}$
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 you run algorithm $\Hello(5)$, how many times is the word "hello" printed?
(a)
14
(b)
16
(c)
13
(d)
15
16 .
Let $X = \{1,2,...,20\}$. You choose a uniformly random 7-element subset $Y$ of $X$. Define the
event
- A = "3 is an element of $Y$ or 13 is an element of $Y$".
(a)
$\frac{2 \cdot {19 \choose 6} - {18 \choose 5}}{{20 \choose 7}}$
(b)
$\frac{2 \cdot {20 \choose 6} - {20 \choose 5}}{{20 \choose 7}}$
(c)
$\frac{{19 \choose 6} + {19 \choose 6}}{{20 \choose 7}}$
(d)
$\frac{2 \cdot {19 \choose 7} - {18 \choose 7}}{{20 \choose 7}}$
17 .
After having proctored the midterm, Alexa, Farah, May, and Shelly decide to go trick-or-treating.
For any house that the ladies visit, if they do not receive candy, they throw rotten eggs at the
house.
Let $m \geq 7$ and $n \geq 7$ be integers. There are $m$ houses whose owners hand out candy and there are $n$ houses whose owners do not hand out candy.
The ladies choose a uniformly random subset of 7 houses and visit these 7 houses. Define the event
Let $m \geq 7$ and $n \geq 7$ be integers. There are $m$ houses whose owners hand out candy and there are $n$ houses whose owners do not hand out candy.
The ladies choose a uniformly random subset of 7 houses and visit these 7 houses. Define the event
- A = "the ladies throw rotten eggs at exactly 2 of the 7 chosen houses".
(a)
$\frac{{m \choose 5} + {n \choose 2}}{{m+n \choose 7}}$
(b)
$\frac{{7 \choose 2}}{{m+n \choose 7}}$
(c)
$\frac{{7 \choose 2}}{{m \choose 5} \cdot {n \choose 2}}$
(d)
$\frac{{m \choose 5} \cdot {n \choose 2}}{{m+n \choose 7}}$