Evaluation: 2019 Winter Final
1 .
Consider strings of length 85, in which each character is one of the letters $a, b, c, d$.
How many such strings have exactly 5 letters $c$?
(a)
${85 \choose 5} \cdot 3^{85}$
(b)
${85 \choose 5} \cdot 3^{80}$
(c)
${85 \choose 5} \cdot 4^{85}$
(d)
${85 \choose 5} \cdot 4^{80}$
2 .
Consider strings of length 85, in which each character is one of the letters $a, b, c, d$.
How many such strings have exactly 15 letters $a$ and exactly 30 letters $d$?
(a)
${85 \choose 15} \cdot {70 \choose 30} \cdot 3^{40}$
(b)
None of the above.
(c)
${85 \choose 15} \cdot {70 \choose 30} \cdot 4^{40}$
(d)
${85 \choose 15} \cdot {70 \choose 30} \cdot 2^{40}$
3 .
Consider a set $S$ consisting of 25 beer bottles $b_1,b_2,...,b_{25}$ and 30 cider bottles $c_1,c_2,...,c_{30}$.
How many 10-element subsets of $S$ contain at least 2 beer bottles?
(a)
${55 \choose 10} - {30 \choose 10} - 25 \cdot {30 \choose 9}$
(b)
${55 \choose 10} - {30 \choose 10} - 25 \cdot {29 \choose 9}$
(c)
${55 \choose 10} - {30 \choose 10} - 25 \cdot {30 \choose 10}$
(d)
${55 \choose 10} - {30 \choose 10} - {30 \choose 9}$
4 .
Consider the sets $A = \{1,2,...,10\}$ and $B = \{1,2,...,14\}$.
Let $S = \{(x,y) : x \in A, y \in B\}$.
An element $(x,y)$ of $S$ is awesome, if $x$ is even or $y$ is even.
What is the number of awesome elements in $S$?
(a)
105
(b)
107
(c)
104
(d)
106
5 .
Let $m \geq 2$ and $n \geq 2$ be integers. Why does the identity
$$
{m + n \choose 2} = {m \choose 2} + {n \choose 2} + mn
$$
hold?
(a)
Because both sides count the number of ordered pairs in a set of size $m + n$.
(b)
Because both sides count the number of ways $m$ men and $n$ women can be arranged on a line,
such that no two men are standing next to each other.
(c)
None of the above.
(d)
Because both sides count the number of 2-element subsets of a set of size $m + n$.
6 .
What is the coefficient of $x^{20}y^{35}$ in the expansion of $(5x - 3y)^{55}$?
(a)
$-{55 \choose 20} \cdot 5^{35} \cdot 3^{20}$
(b)
${55 \choose 20} \cdot 5^{35} \cdot 3^{20}$
(c)
$-{55 \choose 35} \cdot 5^{20} \cdot 3^{35}$
(d)
${55 \choose 35} \cdot 5^{20} \cdot 3^{35}$
7 .
A string that is obtained by rearranging the letters of the word
POOPERSCOOPER
is called cool, if each occurrence of E has the letter R to its left or right, and each occurrence of R has the letter E to its left or right. Thus, bothPOOPERSCOOPER
andOPRECSOOOERPP
are cool, whereasEPOOPRSCOOPER
is not cool. What is the number of cool strings?
(a)
${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 3$
(b)
${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 4$
(c)
${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1}$
(d)
${11 \choose 3} \cdot {8 \choose 4} \cdot {4 \choose 2} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot 2$
8 .
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 1 at position 11 and 0 at position 20? (The positions are numbered $1,2,...,20$.)
What is the number of 00-free bitstrings of length 20 that have 1 at position 11 and 0 at position 20? (The positions are numbered $1,2,...,20$.)
(a)
$f_7 \cdot f_{10}$
(b)
$f_{10} \cdot f_{12}$
(c)
$f_9 \cdot f_{12}$
(d)
$f_8 \cdot f_{11}$
9 .
Consider bitstrings that do not contain 011 and have 1 at every even position.
(The positions are numbered $1,2,3,...$). Let $S_n$ be the number of such strings having
length $n$. Which of the following is true for any $n \geq 3$?
(a)
$S_n = S_{n - 1} + S_{n - 3}$
(b)
$S_n = S_{n - 2} + S_{n - 3}$
(c)
$S_n = 1 + S_{n - 1}$
(d)
$S_n = 1 + S_{n - 2}$
10 .
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is recursively defined as follows:
$$
\begin{align}
f(0) &= 2 \\
f(n) &= 3 \cdot f(n - 1) + 1, \text{ if } n \geq 1
\end{align}
$$
Which of the following is true for all integers $n \geq 0$?
(a)
$f(n) = \frac{3}{2} \cdot 3^n - \frac{1}{2}$
(b)
$f(n) = \frac{5}{2} \cdot 3^n - \frac{1}{2}$
(c)
None of the above.
(d)
$f(n) = \frac{5}{2} \cdot 3^n - 1$
11 .
You flip a fair coin 6 times; the flips are independent of each other.
What is the probability that in these 6 coin flips, the coin comes up heads exactly
3 times?
(a)
5/16
(b)
6/16
(c)
3/16
(d)
4/16
12 .
In a standard deck of 52 cards, each card has a suit and a rank.
There are four suits (spades ♠, hearts ♡, clubs ♣, and diamonds ♢), and 13 ranks
(Ace, 2,3,4,5,6,7,8,9,10, Jack, Queen, and King).
Assume you get a uniformly random hand consisting of 5 cards. What is the probability that the 5 cards in this hand consist of 3 Aces and 2 Queens?
Assume you get a uniformly random hand consisting of 5 cards. What is the probability that the 5 cards in this hand consist of 3 Aces and 2 Queens?
(a)
$\left. 24 \middle/ {52 \choose 5} \right.$
(b)
$\left. 26 \middle/ {52 \choose 5} \right.$
(c)
$\left. 25 \middle/ {52 \choose 5} \right.$
(d)
$\left. 27 \middle/ {52 \choose 5} \right.$
13 .
You flip a fair coin 6 times; the flips are independent of each other. Consider the events
- A = "exactly 3 flips result in heads",
- B = "at least 2 flips result in heads".
(a)
17/57
(b)
18/57
(c)
19/57
(d)
20/57
14 .
Let $n$ and $k$ be integers with $0 \leq k \leq n$.
You are given two bitstrings $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$, both of length $n$. In both bitstrings, each bit is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
For each $i$ with $1 \leq i \leq n$, let $c_i = a_i - b_i$. Consider the set $$ P = \{i : 1 \leq i \leq n \text{ and } c_i \geq 0\}. $$ What is the probability that the size of the set $P$ is equal to $k$?
You are given two bitstrings $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$, both of length $n$. In both bitstrings, each bit is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
For each $i$ with $1 \leq i \leq n$, let $c_i = a_i - b_i$. Consider the set $$ P = \{i : 1 \leq i \leq n \text{ and } c_i \geq 0\}. $$ What is the probability that the size of the set $P$ is equal to $k$?
(a)
${n \choose k} \cdot (3/4)^k \cdot (1/2)^k$
(b)
None of the above.
(c)
${n \choose k} \cdot (3/4)^k \cdot (1/4)^{n - k}$
(d)
${n \choose k} \cdot (3/4)^{n - k} \cdot (1/4)^k$
15 .
Consider a uniformly random permutation $a_1,a_2,a_3,a_4,a_5$ of the set $\{1,2,3,4,5\}$.
Consider the events
- A = "$a_1$ is odd",
- B = "$a_5$ is even".
(a)
None of the above.
(b)
The events $A$ and $B$ are independent.
(c)
All of the above.
(d)
The events $A$ and $B$ are not independent.
16 .
You roll a fair red die once and you roll a fair blue die once. These two rolls are independent.
Consider the events
- A = "the sum of the red die and the blue die is 5",
- B = "the result of the red die is even".
(a)
The events $A$ and $B$ are independent.
(b)
None of the above.
(c)
All of the above.
(d)
The events $A$ and $B$ are not independent.
17 .
Let $n \geq 8$ be an integer. Consider a uniformly random permutation $a_1,a_2,...,a_n$ of
the set $\{1,2,...,n\}$. Consider the events
- A = "$a_7$ is the minimum of $a_1,a_2,...,a_7$",
- B = "$a_6$ is the minimum of $a_1,a_2,...,a_6$".
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
(d)
All of the above.
18 .
Let $A$ and $B$ be two independent events in some sample space $S$. Recall that $\overline{B}$
denotes the complement of $B$. You are given that $\Pr(A) = 1/4$ and $\Pr(\overline{B}) = 2/3$.
What is $\Pr(A \cup B)$?
(a)
1/2
(b)
3/4
(c)
1/3
(d)
2/3
19 .
A red box contains the numbers 0, 1, and 2; a blue box contains the numbers 0 and 1;
and a green box contains the numbers 1 and 2. Consider the following two steps:
Step 1: Choose a uniformly random number from
the red box, and denote it by $x$.
Step 2:
Step 2:
- If $x = 0$ or $x = 2$, then choose a uniformly random number from the green box, and denote it by $y$.
- Otherwise (i.e., if $x = 1$), choose a uniformly random number from the blue box, and denote it by $y$.
- X = the number $x$ you choose in Step 1,
- Y = the number $y$ you choose in Step 2,
- Z = $\max(X,Y).$
(a)
1
(b)
3/2
(c)
2
(d)
None of the above.
20 .
Let $n \geq 2$ be an integer. Consider a string $c_1,c_2,...,c_n$ of length $n$, in which each character
$c_i$ is a uniformly random element of the set $\{1,2,3\}$ (independently of all other characters).
Consider the random variable $X$ whose value is the number of indices $i$ with $1 \leq i < n$ for
which the product $c_i \cdot c_{i + 1}$ is odd.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$\frac{4}{9} \cdot (n - 1)$
(b)
$\frac{2}{3} \cdot n$
(c)
$\frac{2}{3} \cdot (n - 1)$
(d)
$\frac{4}{9} \cdot n$
21 .
Let $n \geq 2$ be an integer. You are given $n$ beer bottles $B_1,B_2,...,B_n$ and two cider bottles $C_1$ and $C_2$.
Consider a uniformly random permutation of these $n + 2$ bottles. The positions in this permutation are
numbered $1,2,...,n + 2$. Consider the random variable
- X = the position of the leftmost beer bottle.
(a)
$\frac{n}{n + 2} + \frac{4n + 2}{(n + 1)(n + 2)}$
(b)
$\frac{n}{n + 2} + \frac{2n + 2}{(n + 1)(n + 2)}$
(c)
$\frac{n}{n + 2} + \frac{2n + 6}{(n + 1)(n + 2)}$
(d)
$\frac{n}{n + 2} + \frac{4n + 6}{(n + 1)(n + 2)}$
22 .
When a couple has a child, this child is a boy with probability 1/2 and a girl with probability 1/2,
independent of the gender of the other children. A couple stops having children as soon as they have
2 girls or 2 boys. Consider the random variables
- G = the number of girls the couple has,
- B = the number of boys the couple has.
(a)
All of the above.
(b)
The random variables $G$ and $B$ are independent.
(c)
None of the above.
(d)
The random variables $G$ and $B$ are not independent.
23 .
You are given a fair red die and a fair blue die. Consider the following experiment:
Consider the random variable
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Experiment: Roll each die once and take the sum of the two rolls.
You repeat this experiment until the sum of the two rolls is equal to 7.Consider the random variable
- X = the number of times you do the experiment.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
5
(b)
6
(c)
3
(d)
4
24 .
Let $n \geq 2$ be an integer, and let $p$ and $q$ be real numbers with $0 < p < 1$ and $0 < q < 1$.
Consider $n$ students $S_1,S_2,...,S_n$ who hand in an assignment for COMP 2804. This assignment has 2 questions. For $i = 1,2,...,n$ let $A_i$ be the assignment handed in by student $S_i$.
Alexa and Zoltan are TAs for the course. Alexa is supposed to mark the first question, whereas Zoltan is supposed to mark the second question. Since both TAs are lazy, they use the following scheme (all random choices are mutually independent):
For $i = 1,2,...,n$,
Hint: Use indicator random variables.
Consider $n$ students $S_1,S_2,...,S_n$ who hand in an assignment for COMP 2804. This assignment has 2 questions. For $i = 1,2,...,n$ let $A_i$ be the assignment handed in by student $S_i$.
Alexa and Zoltan are TAs for the course. Alexa is supposed to mark the first question, whereas Zoltan is supposed to mark the second question. Since both TAs are lazy, they use the following scheme (all random choices are mutually independent):
For $i = 1,2,...,n$,
- Alexa marks the first question of assignment $A_i$ with probability $p,$
- Zoltan marks the second question of assignment $A_i$ with probability $q.$
- X = the number of assignments that are marked by both Alexa and Zoltan.
Hint: Use indicator random variables.
(a)
$(p + q) \cdot n$
(b)
None of the above.
(c)
$p \cdot q \cdot n$
(d)
$\frac{n}{p \cdot q}$