Evaluation: 2018 Winter Midterm

1 . Consider strings consisting of 12 characters, where each character is an element of the set $\{a,b,c,d,e\}$. The positions in such strings are numbered as $1,2,3,\dots,12$.
How many such strings have the property that

• each even position contains an element of $\{a,b,c\}$, and
• each odd position contains an element of $\{d,e\}$?

2 . Consider strings consisting of 12 characters, where each character is an element of the set $\{a,b,c,d,e\}$. The positions in such strings are numbered as $1,2,3,\dots,12$.
How many such strings have the property that

• each even position contains an element of $\{a, b, c\}$, or
• each odd position contains an element of $\{d,e\}$?

3 . Consider strings consisting of 12 characters, where each character is an element of the set $\{a,b,c,d,e\}$. The positions in such strings are numbered as $1,2,3,\dots,12$.
How many such strings contain at least two $a$'s?

4 . Let $b \geq 1$ and $c \geq 1$ be integers. Elisa Kazan's neighborhood pub serves $b$ different types of beer and $c$ different types of cider. Elisa invites 6 friends to this pub and orders 7 drinks, one drink (beer or cider) for each friend, and one cider for herself. Different people may get the same type of beer or cider.
In how many ways can Elisa place these orders, such that exactly 4 people get a beer?

5 . In a group of 100 people,

• 60 do not like Donald Trump and do not like Kim Jong Un, and
• 25 like Kim Jong Un.

How many people in this group like Donald Trump and do not like Kim Jong Un?

6 . In the city of ShortLastName, every person has a last name consisting of one uppercase letter, followed by two lowercase letters. No two letters in a last name can be equal. Thus, Lin is a valid last name, whereas Xax is not a valid last name.
What is the minimum size of the population of ShortLastName, such that there must be at least two people who have the same last name?

7 . Let $n \geq 2$ be an even integer. What does $$ \sum_{k=0}^{\left. (n-2) \middle/ 2 \right.} {{n}\choose{2k+1}} $$ count?

8 . Let $m \geq 34$ be an even integer, let $n \geq 1$ be an integer, and consider the two sets $$ A = \{1,2,\dots,m\} $$ and $$ B = \{m+1,m+2,\dots,m+n\}. $$ Let $k$ be an integer with $17 \leq k \leq n+17$.
Consider subsets $X$ of $A \cup B$, such that $|X| = k, |X \cap A| = 17$, and all elements of $X \cap A$ are even.
How many such subsets $X$ are there?

9 . Consider the equation $$ x_1 + x_2 + x_3 + x_4 = 33, $$ where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$ are integers. How many solutions does this equation have?

10 . As you all know, Nick has been dreaming to be like Spiderman. Spiderman can climb up the outside of a building; if he is at a particular floor, then, in one step, Spiderman can move up several floors.
Since having finished marking assignment 2, Nick has been working hard to improve his Spiderman-skills: In one step, Nick can move up either two floors or three floors. (Nick lost his ability to move up one floor in one step.)
Let $n \geq 2$ be an integer and consider a building with $n$ floors, numbered $1,2,\dots,n$. (The first floor has number 1; this is not the ground floor.) Nick is standing in front of this building, at the ground level.
Let $N_n$ be the number of different ways in which Nick can climb to the $n$-th floor. Which of the following is true for any $n \geq 5$?

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) &= 0, \\ f(n) &= 2 + f(n - 1)\ \; &\mathrm{if}\ n \geq 1, \\ g(0) &= 1, \\ g(n) &= 7 \cdot g(n - 1)\ \; &\mathrm{if}\ n \geq 1. \end{alignat} $$ For any integer $n \geq 0$, what is $g(f(n))$?

13 . Consider strings of characters, where each character is an element of the set $\{a,b,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 bitstrings of length $n$. Which of the following is true?

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

$\mathbf{Algorithm}\ \IFeelLikeSinging(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \mathrm{sing}\ {\it O\ Canada}$
$\mathbf{else}\ \mathbf{if}\ n\ \text{is odd}$
$\elsesp \mathbf{then}\ \IFeelLikeSinging(n + 1)$
$\elsesp \mathbf{else}\ \IFeelLikeSinging(\frac{n}{2});$
$\elsesp \elsesp \IFeelLikeSinging(\frac{n}{2} - 1)$
$\elsesp \mathbf{endif};$
$\mathbf{endif}$

If you run algorithm $\IFeelLikeSinging(9)$, how many times do you sing O Canada?

15 . You are given a fair die and roll it 12 times. Define the event

• A = "there are exactly two 6's in the sequence of 12 rolls".

What is $\Pr(A)$?

16 . In the fall term of 2015, Nick took COMP 2804. Nick was always sitting in the back of the classroom and spent most of his time eating bananas.
Nick buys 25 bananas at Alexa's Banana Emporium (ABE) and 30 bananas at Shelly's Fruit Market (SFM). Nick chooses, uniformly at random, a 15-element subset of these bananas. Define the event

• A = "the subset chosen by Nick contains exactly 7 bananas from ABE".

What is $\Pr(A)$?