Evaluation: 2018 Fall Midterm

1 . Let $n \geq 3$ be an integer and let $S$ be a set consisting of $n$ elements. How many ordered triples $(A, B, C)$ are there for which $A \subseteq S$, $B \subseteq S$, $C \subseteq S$, and $A$, $B$, and $C$ are pairwise disjoint?

2 . Consider bitstrings of length 9. The positions in these strings are numbered as $1,2,3,\dots,9$. How many such bitstrings have the property that

• the bit at each even position is 0, or
• the bitstring starts with 1010?

3 . Consider strings of length 15, where each character is a lowercase letter or an uppercase letter. How many such strings contain at least two lowercase letters?

4 . Elisa Kazan's neighborhood pub serves 8 different types of cider; denote these types by $C_1,C_2,\dots,C_8$. Elisa invites 7 friends to this pub and orders one cider for each friend. Different friends may get the same type of cider. (Elisa came by car and, therefore, orders a glass of water for herself.)
In how many ways can Elisa place these orders of cider, such that exactly 4 of her friends get a cider of type $C_3$?

5 . Consider the equation $$ x_1 + x_2 + x_3 + x_4 + x_5 = 17. $$ How many solutions $(x_1, x_2, x_3, x_4, x_5)$ does this equation have, where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$, and $x_5 \geq 0$ are all integers?

6 . Let $S$ be a subset of the set $\{1,2,3,\dots,50\}$.
What is the minimum size of this subset $S$, such that there must be at least two elements in $S$ whose sum is equal to 51?

7 . Consider 5-element subsets $\{x_1,x_2,x_3,x_4,x_5\}$ of the set $\{1,2,3,\dots,17\}$, where $x_1 < x_2 < x_3 < x_4 < x_5$.
How many such subsets have the property that $x_3 = 7$?

8 . Consider a set $\mathcal{B} = \{B_1,B_2,\dots,B_{13}\}$ of 13 beer bottles and a set $\mathcal{C} = \{C_1,C_2,\dots,C_{12}\}$ of 12 cider bottles.
Consider subsets $X$ of $\mathcal{B} \cup \mathcal{C}$, such that $X$ consists of exactly 5 beer bottles and all cider bottles in $X$ have an even index.
How many such subsets $X$ are there?

9 . A bitstring $s_1s_2...s_n$ is called a palindrome, if $$s_1s_2...s_{n-1}s_n = s_ns_{n-1}...s_2s_1,$$ i.e., reading the string from left to right gives the same string as when reading from right to left.
For any integer $n \geq 1$, let $P_n$ be the number of bitstrings of length $n$ that are palindromes.
Which of the following is true for any integer $n \geq 3$?

10 . Let $n \geq 1$ be an integer and consider a set $\mathcal{B} = \{B_1,B_2,\dots,B_n\}$ of $n$ beer bottles and a set $\mathcal{C} = \{C_1,C_2,\dots,C_n\}$ of $n$ cider bottles.
For any integer $k$ with $0 \leq k \leq n$, consider subsets $X$ of $\mathcal{B} \cup \mathcal{C}$, such that $X$ consists of exactly $k$ bottles and no two bottles in $X$ have the same index. (For example, if $B_n \in X$, then $C_n \notin X$.)
Let $F(n,k)$ be the number of such subsets X.
Which of the following is true for all integers $n \geq 2$ and $k$ with $1 \leq k \leq n - 1$?

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 55 that have 0 at position 9, and 1 at position 40? (The positions are numbered $1,2,\dots,55$.)

12 . The functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ are recursively defined as follows: $$ \begin{alignat}{2} f(0) &= 3, \\ f(n) &= 5 + f(n - 1)\ \; &\mathrm{if}\ n \geq 1, \\ g(0) &= 1, \\ g(n) &= 2 \cdot g(n - 1) &\mathrm{if}\ n \geq 1. \end{alignat} $$ For any integer $n \geq 0$, what is $f(g(n))$?

13 . Consider strings of characters, where each character is one of the 26 lowercase letters $a,b,c,\dots,z$. Such a string is called $qq$-free, if it does not contain two $q$'s next to each other. For any integer $n \geq 1$, let $Q_n$ be the number of $qq$-free strings of length $n$.
Which of the following is true for any integer $n \geq 3$?

14 . Consider the recursive algorithm $\Fart$, which takes as input an integer $n \geq 0$:

$\mathbf{Algorithm}\ \Fart(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \text{eat one can of beans}$
$\mathbf{else}\ \mathbf{if}\ n\ \mathrm{is}\ \mathrm{even}$
$\elsesp \mathbf{then}\ \text{fart once};$
$\elsesp \thensp \Fart \left( n \middle/ 2 \right)$
$\elsesp \mathbf{else}\ \Fart(n + 1);$
$\elsesp \elsesp \text{fart once};$
$\elsesp \elsesp \Fart(n - 1)$
$\elsesp \mathbf{endif};$
$\mathbf{endif}$

If you run algorithm $\Fart(9)$, how many times do you fart?

15 . The Carleton Computer Science Society is organizing their annual Halloween party. At this party,

• one student is dressed up as Donald Trump,
• one student is dressed up as Kim Jong Un,
• the remaining 57 students are dressed up as Kim Kardashian.

These students are arranged, uniformly at random, on a line.
Define the event,

• A = "Donald Trump is standing next to Kim Jong Un".

What is $\Pr(A)$?

16 . Alexa, Tri, and Zoltan each have a uniformly random birthday. (We ignore leap years, so that one year has 365 days.)
Define the event

• A = "Alexa, Tri, and Zoltan have different birthdays".

What is $\text{Pr}(A)$?

17 . This midterm has 17 questions. For each question, four options are given. Assume that you answer each question, by choosing one of the four options uniformly at random.
Define the event

• A = "you answer exactly 7 questions correctly".

What $\Pr(A)$?