Evaluation: 2017 Fall Final
1 .
You are given 20 beer bottles $B_1,B_2,\dots,B_{20}$ and 30 cider bottles $C_1,C_2,\dots,C_{30}$.
Assume you arrange these 50 bottles on a horizontal line such that
- the leftmost 10 bottles are all beer bottles, and
- the rightmost 10 bottles are all cider bottles.
(a)
${20 \choose 10} \cdot {30 \choose 10} \cdot 30!$
(b)
${20 \choose 10} \cdot 10! \cdot {30 \choose 10} \cdot 10!$
(c)
${20 \choose 10} \cdot 10! \cdot {30 \choose 10} \cdot 10! \cdot 30!$
(d)
$50!$
2 .
Let $n \geq 2$ be an even integer. A permutation $a_1,a_2,\dots,a_n$ of the set $\{1,2,\dots,n\}$ is
called awesome if $a_2 = 2 \cdot a_1$.
For example, if $n = 6$, then the permutation $3,6,4,1,5,2$ is awesome, whereas the permutation $3,5,4,1,6,2$ is not awesome.
How many awesome permutations of the set $\{1,2,\dots,n\}$ are there?
For example, if $n = 6$, then the permutation $3,6,4,1,5,2$ is awesome, whereas the permutation $3,5,4,1,6,2$ is not awesome.
How many awesome permutations of the set $\{1,2,\dots,n\}$ are there?
(a)
$n \cdot (n-2)!$
(b)
${\frac{n}{2}} \cdot (n-1)!$
(c)
$n \cdot (n-1)!$
(d)
${\frac{n}{2}} \cdot (n-2)!$
3 .
Consider strings consisting of 40 characters, where each character is one of the letters $a$, $b$, and
$c$. Such a string is called cool if
- it contains exactly 8 many $a$'s
- it contains exactly 7 many $b$'s.
(a)
$ {{40 \choose 8} \cdot 2^{32} + {40 \choose 7} \cdot 2^{33}}$
(b)
$ {{40 \choose 8} \cdot 2^{32} + {40 \choose 7} \cdot 2^{33} - {40 \choose 15} \cdot {15 \choose 8}} $
(c)
$ {{40 \choose 8} \cdot 2^{32} + {40 \choose 7} \cdot 2^{33} - {40 \choose 15} \cdot {15 \choose 8} \cdot 2^{25}} $
(d)
None of the above.
4 .
Consider strings consisting of 40 characters, where each character is one of the letters $a$, $b$, and
$c$. How many such strings contain at least three $a$'s?
(a)
$3^{40} - 2^{40} - 40 \cdot 2^{39} - {40 \choose 2} \cdot 2^{38} -$ $ {40 \choose 3} \cdot 2^{37}$
(b)
$3^{40} - 1 - 40 \cdot 3^{39} - {40 \choose 2} \cdot 3^{38}$
(c)
$3^{40} - 2^{40} - 40 \cdot 2^{39} - {40 \choose 2} \cdot 2^{38}$
(d)
${40 \choose 3}$
5 .
Let $n \geq 3$ and $m \geq 3$ be integers. What does
$$
{n \choose 3} + {m \choose 3} + n \cdot {m \choose 2} + m \cdot {n \choose 2}
$$
count?
(a)
The number of subsets having size 3 of a set consisting of $n$ positive numbers and $m$ negative numbers.
(b)
The number of subsets having size 2 or 3 of a set consisting of $n$ positive numbers and $m$ negative numbers.
(c)
The number of subsets having size 2 and 3 of a set consisting of $n$ positive numbers and $m$ negative numbers.
(d)
The number of subsets having size at most 3 of a set consisting of $n$ positive numbers and $m$ negative numbers.
6 .
Consider a group of 100 students. In this group,
- 13 students like Donald Trump,
- 25 students like Justin Bieber, and
- 8 students like Donald Trump and like Justin Bieber.
(a)
71
(b)
70
(c)
72
(d)
69
7 .
How many strings can be obtained by rearranging the letters of the word
BOOKKEEPER
(a)
$2! \cdot 2! \cdot 3!$
(b)
${10 \choose 2} \cdot {8 \choose 2} \cdot {6 \choose 3} \cdot {3 \choose 2}$
(c)
${10 \choose 2} \cdot {8 \choose 2} \cdot {6 \choose 3} \cdot 3 \cdot 2$
(d)
${10 \choose 2} \cdot {8 \choose 2} \cdot {5 \choose 3} \cdot 3 \cdot 2$
8 .
Consider strings consisting of characters, where each character is one of the letters $a$, $b$, and
$c$.
For any integer $n \geq 1$, let $E_n$ be the number of such strings of length $n$ that contain an even number of $c$'s, and let $O_n$ be the number of such strings of length $n$ that contain an odd number of $c$'s. (Remember that 0 is an even number.)
Which of the following is true for any integer $n \geq 2$?
For any integer $n \geq 1$, let $E_n$ be the number of such strings of length $n$ that contain an even number of $c$'s, and let $O_n$ be the number of such strings of length $n$ that contain an odd number of $c$'s. (Remember that 0 is an even number.)
Which of the following is true for any integer $n \geq 2$?
(a)
$E_n = 2 \cdot O_{n-1} + E_{n-1}$
(b)
$E_n = 2 \cdot O_{n-1} + O_{n-1}$
(c)
$E_n = 2 \cdot E_{n-1} + E_{n-1}$
(d)
$E_n = 2 \cdot E_{n-1} + O_{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} + S_{n-3}$
(b)
$S_n = S_{n-1} + S_{n-2} + 1$
(c)
$S_n = S_{n-1} + S_{n-2} + 2^{n-2}$
(d)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$
10 .
$\newcommand{\IFeelLikeSinging}{{\rm IF {\scriptsize EEL} L {\scriptsize IKE} S {\scriptsize INGING}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
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}$
(a)
8
(b)
9
(c)
7
(d)
6
11 .
Assume you write a multiple-choice exam that has 25 questions. For each question, four options are given
to you, and exactly one of these options is the correct answer.
Assume that you answer each question uniformly at random, where the choices for different questions are independent of each other.
What is the probability that you have exactly 17 correct answers?
Assume that you answer each question uniformly at random, where the choices for different questions are independent of each other.
What is the probability that you have exactly 17 correct answers?
(a)
${25 \choose 17} \cdot \left( 3 \middle/ 4 \right)^{17}$
(b)
${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^8 \cdot \left( 3 \middle/ 4 \right)^{17}$
(c)
${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^{17}$
(d)
${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^{17} \cdot \left( 3 \middle/ 4 \right)^8$
12 .
A bitstring $b_1b_2{\dots}b_n$ of length $n$ is called a palindrome if
$$
b_1b_2{\dots}b_{n-1}b_n = b_nb_{n-1}{\dots}b_2b_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 2$ be an even integer. You are given a uniformly random bitstring of length $n$. What is the probability that this bitstring is a palindrome?
Let $n \geq 2$ be an even integer. You are given a uniformly random bitstring of length $n$. What is the probability that this bitstring is a palindrome?
(a)
$1/2$
(b)
$(1/2)^{n}$
(c)
$(1/2)^{n/2}$
(d)
$(1/2)^{2n}$
13 .
Let $X = \{1,2,3,\dots,10\}$. Let $Y$ be a uniformly random subset of $X$. Define the events
- A = "$Y$ contains at least 4 elements",
- B = "all elements of $Y$ are even".
(a)
6/16
(b)
5/16
(c)
3/16
(d)
4/16
14 .
Let $n \geq 1$ be an integer. You are given two bitstrings $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ 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).
Consider the string $$ a_1 + b_1,a_2 + b_2,\dots,a_n + b_n. $$ 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_n + b_n. $$ What is the probability that each element in this string is non-zero?
(a)
$1 - (3/4)^{n}$
(b)
$(1/4)^{n}$
(c)
$1 - (1/4)^{n}$
(d)
$(3/4)^{n}$
15 .
You flip a fair coin three times; these three flips are independent. Define the events
- A = "the first two flips both result in heads",
- B = "there are at least two heads in the sequence of three flips".
(a)
The events $A$ and $B$ are independent.
(b)
The events $A$ and $B$ are not independent.
(c)
None of the above.
16 .
You choose a uniformly random element, say $x$, from the set $\{1,2,3\}$, and you choose a uniformly
random element, say $y$, from the same set $\{1,2,3\}$. ($x$ and $y$ are chosen independently of
each other.) Define the events
- A = "$x$ is odd",
- B = "$x + y$ is odd".
(a)
The events $A$ and $B$ are not independent.
(b)
None of the above.
(c)
The events $A$ and $B$ are independent.
17 .
Let $X = \{1,2,\dots,100\}$. Let $Y$ be a uniformly random 7-element subset of $X$. Define the event
- A = "the set $Y$ contains at least one even number".
(a)
$\frac{{50 \choose 7}}{{100 \choose 7}}$
(b)
$(1/2)^{7}$
(c)
$1 - (1/2)^{7}$
(d)
$1 - \frac{{50 \choose 7}}{{100 \choose 7}}$
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 = $\max(X,Y).$
(a)
1
(b)
1/2
(c)
1/4
(d)
3/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 \neq b_{i+1}$.
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 \neq b_{i+1}$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$\frac{n}{2}$
(b)
None of the above.
(c)
$\frac{n-1}{2}$
(d)
$\frac{n+1}{2}$
20 .
You choose a uniformly random element, say $a$, from the set $\{1,2,\dots,100\}$, and you choose a
uniformly random element, say $b$, from the same set $\{1,2,\dots,100\}$. ($a$ and $b$ are chosen
independently of each other.) Define the random variable $X$ to be
- X = $\max(a,b)$.
(a)
${\sum_{k=1}^{100}} k \cdot \frac{k^{2}}{100^{2}}$
(b)
${\sum_{k=1}^{100}} k \cdot \left( \frac{1+2(k-1)}{100^{2}} \right)$
(c)
${\sum_{k=1}^{100}} k \cdot \frac{2k}{100^{2}}$
(d)
${\sum_{k=1}^{100}} k \cdot \frac{k(k-1)}{100^{2}}$
21 .
You are given a fair red die and a fair blue die. You roll each die once, independently of each
other. Let $(i,j)$ be the outcome, where $i$ is the result of the red die and $j$ is the result of
the blue die. Define the random variables
$$
X = i + j
$$
and
$$
Y = i - j.
$$
Which of the following is true?
(a)
None of the above.
(b)
The random variables $X$ and $Y$ are independent.
(c)
The random variables $X$ and $Y$ 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 May 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{May rolls the die, let m be the result}$
$\quad \quad \mathbf{if}\ a > m\ \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 < m\ \mathbf{then}$
$\quad \quad \quad \text{print May goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a = m\ \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)
6/5
(b)
5/6
(c)
3/2
(d)
5/4
23 .
Is the following statement true or false?
For any random variable $X$, $\mathbb{E}\left(1 \middle/ X \right) = 1 / \mathbb{E}(X)$.
(a)
The statement is false.
(b)
None of the above.
(c)
The statement is true.
24 .
Let $n$ and $k$ be integers such that $n$ is even, $n \geq 2$, and $1 \leq k \leq n$.
The Carleton Computer Science Society (CCSS) is having their annualChristmas Holiday Season Party, which
is attended by $n$ students.
Consider a uniformly random permutation of these $n$ students. The positions in this permutation are numbered
as $1,2,...,n$.
Define the following random variable $X$:
Hint: Use indicator random variables.
The Carleton Computer Science Society (CCSS) is having their annual
| (a) | $k$ of these $n$ students are politically correct and, thus, refuse to say Merry Christmas. Instead, they say Happy Holidays. |
| (b) | $n - k$ of these $n$ students do not care about political correctness and, thus, they say Merry Christmas. |
Define the following random variable $X$:
- X = the number of positions $i$ with $1 \leq i \leq \left. n \middle/ 2 \right.$ such that both students at positions $i$ and $2i$ are politically correct.
Hint: Use indicator random variables.
(a)
$n \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$
(b)
$\frac{n}{2} \cdot \frac{k(k - 1)}{n(n - 1)}$
(c)
$\frac{n}{2} \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$
(d)
$n \cdot \frac{k(k - 1)}{n(n - 1)}$