Evaluation: 2018 Winter Final
1 .
You are given 20 beer bottles $B_1,B_2,\dots,B_{20}$ and 50 cider bottles $C_1,C_2,\dots,C_{50}$.
Consider subsets of these 70 bottles, consisting of 30 bottles, exactly 12 of which are beer
bottles. How many subsets are there?
(a)
${20 \choose 12} \cdot {38 \choose 18}$
(b)
${20 \choose 12} \cdot {50 \choose 18}$
(c)
${70 \choose 30} \cdot {20 \choose 12}$
(d)
${50 \choose 12} \cdot {20 \choose 18}$
2 .
You are given 20 beer bottles $B_1,B_2,\dots,B_{20}$ and 50 cider bottles $C_1,C_2,\dots,C_{50}$.
Consider subsets of these 70 bottles, that contain exactly 12 beer bottles (and any number of cider
bottles) or exactly 12 cider bottles (and any number of beer bottles). How many such subsets are
there?
(a)
${20 \choose 12} + {50 \choose 12}$
(b)
${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20}$
(c)
${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20} - {20 \choose 12} \cdot {50 \choose 12}$
(d)
${20 \choose 12} + {50 \choose 12} - {20 \choose 12} \cdot {50 \choose 12}$
3 .
You are given 20 beer bottles $B_1,B_2,\dots,B_{20}$ and 50 cider bottles $C_1,C_2,\dots,C_{50}$.
Consider subsets of these 70 bottles, that contain at least 3 beer bottles (and any number of cider
bottles). How many such subsets are there?
(a)
None of the above.
(b)
$2^{70} - 2^{50} - 20 - {20 \choose 2}$
(c)
$2^{70} - 2^{50} - 20 \cdot 2^{50}$
(d)
$2^{70} - 2^{50} - 20 \cdot 2^{50} - {20 \choose 2} \cdot 2^{50}$
4 .
Consider strings consisting of 40 characters, where each character is an element of $\{a,b,c,d\}$.
How many such strings contain exactly five $a$'s or exactly five $c$'s?
(a)
$2 \cdot {40 \choose 5} \cdot 3^{35}$
(b)
$2 \cdot {40 \choose 5} - {40 \choose 5} \cdot {35 \choose 5}$
(c)
$2 \cdot {40 \choose 5} \cdot 3^{35} - {40 \choose 5} \cdot {35 \choose 5} \cdot 2^{30}$
(d)
${40 \choose 5} + {35 \choose 5} - {40 \choose 5} \cdot {35 \choose 5}$
5 .
Let $m \geq 2$ and $n \geq 2$ be integers. What does
$$
{m \choose 2} + {n \choose 2} + m \cdot n
$$
count?
(a)
The number of ways to choose a 2-element subset from a set consisting of $m + n$ elements.
(b)
None of the above.
(c)
The number of ways to choose a subset from a set consisting of $m + n$ elements.
(d)
The number of ways to choose an ordered pair of 2 elements from a set consisting of $m + n$ elements.
6 .
Nick (your friendly TA) eats lots of bananas. During a period of 7 days, Nick eats a total of 25 bananas. A banana
schedule is a sequence of 7 numbers, whose sum is equal to 25, and whose numbers indicate the number
of bananas that Nick eats on each day. Three examples of such schedules are (3,2,7,4,1,3,5),
(2,3,7,4,1,3,5), and (3,0,9,4,1,0,8). How many banana schedules are there?
(a)
${32 \choose 7}$
(b)
${32 \choose 6}$
(c)
${31 \choose 7}$
(d)
${31 \choose 6}$
7 .
A string that is obtained by rearranging the letters of the word
BOOGER
is called awesome, if the string does not contain the substring OO. Thus, GEOROB is awesome, whereas GREOOB is not awesome. What is the number of awesome strings?
(a)
$(6 \cdot {5 \choose 2} \cdot 3 \cdot 2) - 5!$
(b)
$(6 \cdot {5 \choose 2} \cdot 3) - 5!$
(c)
$6! - 5!$
(d)
$6 \cdot {5 \choose 2} \cdot 3 \cdot 2$
8 .
Consider strings consisting of characters, where each character is an element of $\{a, b, c, d\}$.
Such a string is called valid, if it does not contain $aa$, it does not contain $bb$,
it does not contain $cc$, and it does not contain $dd$.
For any integer $n \geq 2$, what is the number of valid strings of length $n$?
For any integer $n \geq 2$, what is the number of valid strings of length $n$?
(a)
$4^{n} - 4(n-1)$
(b)
$4 \cdot 3^{n}$
(c)
$4^{n} - 4n$
(d)
$4 \cdot 3^{n-1}$
9 .
Consider bitstrings that do not contain 110. Let $S_n$ be the number of such strings having length
$n$. Which of the following is true for any $n \geq 4$?
(a)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$
(b)
$S_n = S_{n-1} + S_{n-2} + 2^{n-2}$
(c)
$S_n = S_{n-1} + S_{n-2} + 1$
(d)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
10 .
$\newcommand{\SundayEveningExam}{{\rm S {\scriptsize UNDAY} E {\scriptsize VENING} E {\scriptsize XAM}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the recursive algorithm $\SundayEveningExam$, which takes as input an integer $n \geq 1$:
(see file for removed code)
Let $P(n)$ be the number of times the line "I don't like Sunday evening exams" is printed when running
algorithm $\SundayEveningExam(n)$. Which of the following is true for all $n \geq 1$?
(a)
$P(n) = \frac{n(n-1)}{2}$
(b)
$P(n) = 1 + \frac{n(n+1)}{2}$
(c)
$P(n) = 1 + \frac{n(n-1)}{2}$
(d)
$P(n) = \frac{n(n+1)}{2}$
11 .
You roll a fair die 18 times; the rolls are independent of each other. What is the probability that
you roll a 5 exactly three times?
(a)
None of the above.
(b)
${18 \choose 3} \cdot \left(5 \middle/ 6 \right)^{18}$
(c)
$18 \cdot \left. 5^{15} \middle/ 6^{18} \right.$
(d)
${18 \choose 3} \cdot \left. 5^{15} \middle/ 6^{18} \right.$
12 .
A string $s_1s_2{\dots}s_n$ is called a palindrome, if
$$
s_1s_2{\dots}s_{n-1}s_n = s_ns_{n-1}{\dots}s_2s_1,
$$
i.e., reading the string from left to right gives the
same result as reading the string from right to left.
Let $n \geq 3$ be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this string is a palindrome?
Let $n \geq 3$ be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this string is a palindrome?
(a)
$(1/2)^{(n+1)/2}$
(b)
$(1/3)^{(n+1)/2}$
(c)
$(1/2)^{(n-1)/2}$
(d)
$(1/3)^{(n-1)/2}$
13 .
You are given a uniformly random bitstring of length five. Define the events
- A = "the bitstring contains at most four 1's",
- B = "the bitstring contians an odd number of 1's".
(a)
15/16
(b)
14/16
(c)
13/16
(d)
12/16
14 .
You are given two bitstrings $a_1,a_2,\dots,a_{77}$ and $b_1,b_2,\dots,b_{77}$ of length 77. In
both bitstrings, each bit is 0 with probability 3/4, and 1 with probability 1/4 (independent of
all other bits).
Consider the string $$ a_1-b_1,a_2-b_2,\dots,a_{77}-b_{77}. $$ What is the probability that each element in this string is non-zero?
Consider the string $$ a_1-b_1,a_2-b_2,\dots,a_{77}-b_{77}. $$ What is the probability that each element in this string is non-zero?
(a)
$(3/8)^{77}$
(b)
$(5/8)^{77}$
(c)
$(6/8)^{77}$
(d)
$(4/8)^{77}$
15 .
You flip a fair coin four times; these four flips are independent. Define the events
- A = "the first two flips result (in this order) in $HT$",
- B = "the second and third flips result in $TT$".
(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.
16 .
You flip a fair coin five times; these five flips are independent. Define the events
- A = "the first three flips result in $HHH$",
- B = "the number of $T$ in these five flips is at least two".
(a)
The events $A$ and $B$ are independent.
(b)
The events $A$ and $B$ are not independent.
(c)
All of the above.
(d)
None of the above.
17 .
Let $n \geq 1$ be an integer.
Consider a uniformly random permutation of the set $\{1,2,3,\dots,2n\}$. Define the event
- A = "both the first element and the last element in the permutation are even integers".
(a)
$\frac{n-1}{2(2n-1)}$
(b)
$\frac{2(2n-1)}{n-1}$
(c)
$\frac{n-1}{4n}$
(d)
$\frac{n}{2(2n-1)}$
18 .
You flip a fair red coin once, and you flip a fair blue coin once, independently of each other.
Define the random variables
and
| $X = \bigg\{$ | $1\ $ | if the red coin flip resulted in heads$,$ |
| $0\ $ | if the red coin flip resulted in tails$,$ | |
| $Y = \bigg\{$ | $1\ $ | if the blue coin flip resulted in heads$,$ |
| $0\ $ | if the blue coin flip resulted in tails$,$ |
- Z = $\min(X,Y).$
(a)
1/2
(b)
1
(c)
3/4
(d)
1/4
19 .
Let $n \geq 2$ be an integer. Consider a bitstring $b_1,b_2,\dots,b_n$ of length $n$, in which each
bit $b_i$ is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
Define the random variable $X$ to be the number of indices $i$ with $1 \leq i < n$ for which $b_i \cdot b_{i+1} = 0$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
Define the random variable $X$ to be the number of indices $i$ with $1 \leq i < n$ for which $b_i \cdot b_{i+1} = 0$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$n/4$
(b)
$3n/4$
(c)
$(n-1)/4$
(d)
$3(n-1)/4$
20 .
Let $n \geq 2$ be an integer. You are given $n$ beer bottles $B_1,B_2,\dots,B_n$ and one cider
bottle $C$. Consider a uniformly random permutation of these $n+1$ bottles. The positions in this
permutation are numbered as $1,2,3,\dots,n+1$. Define the random variable $X$ to be
- X = the position of the leftmost beer bottle.
(a)
1
(b)
$\frac{n+1}{n}$
(c)
$\frac{n+2}{n+1}$
(d)
$\frac{n+3}{n+1}$
21 .
You are given two independent random variables $X$ and $Y$, where
Define the random variable $Z = X \cdot Y$. Which of the following is correct?
| $\Pr(X = 0)$ | $= \Pr(X = 1) = \Pr(Y = 0)$ $= \Pr(Y = 1) = 1/2.$ |
(a)
None of the above.
(b)
The random variables $X$ and $Z$ are independent.
(c)
All of the above.
(d)
The random variables $X$ and $Z$ are not independent.
22 .
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
$\newcommand{\WhoGoesFirst}{{\rm W {\scriptsize HO} G {\scriptsize OES} F {\scriptsize IRST}}}
\newcommand{\thensp}{\phantom{\mathbf{then}\ }}$
Alexa and Shelly want to play the game of Monopoly. They use the following recursive algorithm
to decide who goes first:
$\WhoGoesFirst(k):$
$\quad \mathbf{if}\ k \geq 1\ \mathbf{then}$
$\quad \quad \text{Alexa rolls the die, let a be the result}$
$\quad \quad \text{Shelly rolls the die, let s be the result}$
$\quad \quad \mathbf{if}\ a > s\ \mathbf{then}$
$\quad \quad \quad \text{print Alexa goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a < s\ \mathbf{then}$
$\quad \quad \quad \text{print Shelly goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a = s\ \mathbf{then}$
$\quad \quad \quad \WhoGoesFirst(k + 1)$
$\quad \quad \mathbf{endif}$
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
5/6
(b)
3/2
(c)
5/4
(d)
6/5
23 .
Consider the following statement: For any three random variables $X$, $Y$, and $Z$,
- $\mathbb{E}(\min(X,Y,Z)) = \min(\mathbb{E}(X), \mathbb{E}(Y), \mathbb{E}(Z))$
(a)
All of the above.
(b)
The statement is false.
(c)
The statement is true.
(d)
None of the above.
24 .
Elisa Kazan has successfully completed her second year as President of the Carleton Computer Science Society.
In order to celebrate this, Elisa throws a party. She invites 15 students; thus, the total number of students
at the party is equal to 16. Elisa has brought an unlimited amount of drinks: 5 types $C_1,C_2,C_3,C_4,C_5$
of cider and 3 types $B_1,B_2,B_3$ of beer. Each of the 16 students gets 3 drinks; each of these drinks is
uniformly, and independently, chosen from the 8 types of drinks.
Define the following random variable $X$:
Hint: Use indicator random variables.
Define the following random variable $X$:
- X = the number of students who get exactly 2 ciders.
Hint: Use indicator random variables.
(a)
$2^{4} \cdot 3^{2} \left. \cdot 5^{2} \middle/ 8^{3} \right.$
(b)
$2^{4} \cdot 3^{2} \cdot \left. 5^{2} \middle/ 3^{8} \right.$
(c)
$3^{2} \cdot \left. 5^{2} \middle/ 8^{3} \right.$
(d)
$2^{4} \cdot 3^{2} \cdot \left. 2^{5} \middle/ 8^{3} \right.$