Evaluations

Evaluation: 2017 Fall Final

Author: Michiel Smid

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.
How many such arrangements are there? (The order of the bottles matters.)
(a)
$50!$
(b)
${20 \choose 10} \cdot 10! \cdot {30 \choose 10} \cdot 10! \cdot 30!$
(c)
${20 \choose 10} \cdot {30 \choose 10} \cdot 30!$
(d)
${20 \choose 10} \cdot 10! \cdot {30 \choose 10} \cdot 10!$

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?
(a)
${\frac{n}{2}} \cdot (n-1)!$
(b)
$n \cdot (n-2)!$
(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
or
  • it contains exactly 7 many $b$'s.
How many cool strings are there?
(a)
None of the above.
(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}}$
(d)
$ {{40 \choose 8} \cdot 2^{32} + {40 \choose 7} \cdot 2^{33} - {40 \choose 15} \cdot {15 \choose 8} \cdot 2^{25}} $

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} - 1 - 40 \cdot 3^{39} - {40 \choose 2} \cdot 3^{38}$
(b)
$3^{40} - 2^{40} - 40 \cdot 2^{39} - {40 \choose 2} \cdot 2^{38}$
(c)
${40 \choose 3}$
(d)
$3^{40} - 2^{40} - 40 \cdot 2^{39} - {40 \choose 2} \cdot 2^{38} -$ $ {40 \choose 3} \cdot 2^{37}$

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 at most 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 3 of a set consisting of $n$ positive numbers and $m$ negative numbers.
(d)
The number of subsets having size 2 and 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.
How many students do not like Donald Trump and do not 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)
${10 \choose 2} \cdot {8 \choose 2} \cdot {6 \choose 3} \cdot 3 \cdot 2$
(b)
${10 \choose 2} \cdot {8 \choose 2} \cdot {5 \choose 3} \cdot 3 \cdot 2$
(c)
${10 \choose 2} \cdot {8 \choose 2} \cdot {6 \choose 3} \cdot {3 \choose 2}$
(d)
$2! \cdot 2! \cdot 3!$

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$?
(a)
$E_n = 2 \cdot E_{n-1} + O_{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 O_{n-1} + E_{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} + S_{n-3}$
(d)
$S_n = S_{n-1} + S_{n-2} + 1$

10 . 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?
(a)
6
(b)
7
(c)
9
(d)
8

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?
(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} \cdot \left( 3 \middle/ 4 \right)^8$
(d)
${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^{17}$

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?
(a)
$1/2$
(b)
$(1/2)^{n}$
(c)
$(1/2)^{2n}$
(d)
$(1/2)^{n/2}$

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".
What is $\Pr(A|B)$?
(a)
6/16
(b)
4/16
(c)
5/16
(d)
3/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?
(a)
$1 - (1/4)^{n}$
(b)
$1 - (3/4)^{n}$
(c)
$(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".
Which of the following is true?
(a)
The events $A$ and $B$ are not independent.
(b)
None of the above.
(c)
The events $A$ and $B$ are independent.

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".
Which of the following is true?
(a)
The events $A$ and $B$ are not independent.
(b)
The events $A$ and $B$ are independent.
(c)
None of the above.

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".
What is $\Pr(A)$?
(a)
$(1/2)^{7}$
(b)
$1 - \frac{{50 \choose 7}}{{100 \choose 7}}$
(c)
$1 - (1/2)^{7}$
(d)
$\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
$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$,$
and
  • Z = $\max(X,Y).$
What is the expected value $\mathbb{E}(Z)$ of the random variable $Z$?
(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.
(a)
$\frac{n}{2}$
(b)
$\frac{n-1}{2}$
(c)
None of the above.
(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)$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
${\sum_{k=1}^{100}} k \cdot \left( \frac{1+2(k-1)}{100^{2}} \right)$
(b)
${\sum_{k=1}^{100}} k \cdot \frac{k^{2}}{100^{2}}$
(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)
The random variables $X$ and $Y$ are not independent.
(b)
The random variables $X$ and $Y$ are independent.
(c)
None of the above.

22 . 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}$

The ladies run algorithm $\WhoGoesFirst(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
3/2
(b)
5/4
(c)
5/6
(d)
6/5

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 true.
(b)
None of the above.
(c)
The statement is false.

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 annual Christmas Holiday Season Party, which is attended by $n$ students.
(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.
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$:
  • 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.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
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)
$n \cdot \frac{k(k - 1)}{n(n - 1)}$
(d)
$\frac{n}{2} \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$

25 . How do you feel about writing an exam on Friday evening?
(a)
I would rather sit in the pub and have a beer.