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/2 \choose 4} \cdot {n/2 \choose 3}$
(b)
${n \choose 4} \cdot {n \choose 3}$
(c)
${n \choose 4} + {n \choose 3}$
(d)
${n/2 \choose 4} + {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.
These $s+t+k$ students are arranged on a line, such that all Supermen are standing next to each
other, all Trumps are standing next to each other, all Kims are standing next to each other, and no
Trump is standing next to any Kim. How many such arrangements are there?
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)
$n^{7n}$
(b)
$(7n)^{n}$
(c)
$n^{n}$
(d)
$7^{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?
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)
$(n/2) \cdot 2^{n/2}$
(b)
$2^{n} - 2^{n/2}$
(c)
$2^{n/2} + 2^{n/2}$
(d)
$2^{n} + 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)
$4^{n-3} + 4^{n-4}$
(c)
$2 \cdot 4^{n-3} - 4^{n-7}$
(d)
$2 \cdot 4^{n-4} - 4^{n-7}$
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$, $b$, or $c$, that contain at least one $a$.
(c)
The number of strings of length $n$, where each character is $a$ or $b$, that contain at least 2 many $a$'s.
(d)
The number of strings of length $n$, where each character is $a$ or $b$, that contain at least one $a$.
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)
6
(b)
7
(c)
5
(d)
4
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 20} \cdot 7^{80} \cdot 13^{20}$
(d)
$- {100 \choose 80} \cdot 7^{20} \cdot 13^{80}$
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$
(b)
$n+1$
(c)
$n-1$
(d)
$n+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}$.
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_{15}$
(c)
$f_{7} \cdot f_{14}$
(d)
$f_{8} \cdot f_{14}$
12 .
The functions $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ and $g : \mathbb{N} \rightarrow \mathbb{N}$
are recursively defined as follows:
$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.$
For any integer $n \geq 0$, what is $f(g(n), g(n))$?
(a)
$(5^{n})^{2}$
(b)
$2 \cdot 5^{n-1}$
(c)
$(5^{n-1})^{2}$
(d)
$2 \cdot 5^{n}$
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?
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
the bricks exactly cover $B_n$ and
no two bricks overlap.
The figure below shows a tiling of $B_{13}$.
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} + 2 \cdot T_{n - 2}$
(b)
$T_n = T_{n - 1} + T_{n - 2}$
(c)
$T_n = 2 \cdot T_{n - 1} + T_{n - 2}$
(d)
$T_n = 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)
13
(b)
14
(c)
16
(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$".
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
A = "the ladies throw rotten eggs at exactly 2 of the 7 chosen houses".