Evaluation: 2017 Winter Final

1 . Consider permutations $a_1,a_2,\dots,a_{10}$ of the set $\{1,2,\dots,10\}$ for which

• $a_1,a_3,a_5,a_7,a_9$ are all odd and
• $a_2,a_4,a_6,a_8,a_{10}$ are all even.

How many such permutations are there?

2 . Let $n \geq 2$ be an integer. Consider permutations $a_1,a_2,\dots,a_n$ of the set $\{1,2,\dots,n\}$ for which $a_1 < a_2$. How many such permutations are there?

3 . Let $B$ be a set consisting of 45 bottles. Out of these, 17 are beer bottles, and the remaining 28 are cider bottles. Consider subsets of $B$ that contain

• exactly 5 beer bottles and zero or more cider bottles,

or

• exactly 5 cider bottles and zero or more beer bottles.

How many such subsets are there?

4 . A bitstring $b_1b_2 \dots b_n$ is called a palindrome if $b_1b_2 \dots b_n = b_nb_{n-1} \dots b_1$, i.e., reading the string from left to right gives the same result as reading it from right to left. Let $n \geq 3$ be an odd integer. How many palindromes of length $n$ are there?

5 . Let $n \geq 2$ be an integer. What does $2^{n} - 2^{n-2}$ count?

6 . Consider a group of 100 students. In this group,

• 63 students like beer,
• 71 students like cider, and
• 25 students do not like beer and do not like cider.

How many students like beer and cider?

7 . In this question, we consider bitstrings of length $n$, where $n$ is an even integer, and in which the positions are numbered $1,2,\dots,n$.
For any even integer $n$, let $S_n$ be the number of bitstrings of length $n$ that have both of the following two properties:

• There is a 0 at every even position.
• The entire bitstring does not contain the substring 101.

Which of the following is true for all even integers $n \geq 6$?

8 . Consider bitstrings that contain at least one occurrence of 000. Let $S_n$ be the number of such strings having length $n$. Which of the following is true for $n \geq 4$?

9 . Consider the recursive algorithm $\Hello$, which takes as input an integer $n \geq 0$: (see file for missing code) If we run algorithm $\Hello(7)$, how many times is the word "hello" printed?

10 . We choose, uniformly at random, a string consisting of 14 characters, where each character is a lowercase letter. Let $A$ be the event

• A = "the string contains at least one vowel".

(A vowel is one of the letters $a$, $e$, $i$, $o$, and $u$.) What is $\Pr(A)$?

11 . Consider a group consisting of 7 girls and 6 boys. Elisa is one of the girls. How many ways are there to arrange these 13 people on a horizontal line such that Elisa has 2 neighbors, both of whom are girls? (The order on the line matters.)

12 . Let $X = \{1,2,3,\dots,10\}$. We choose, uniformly at random, a subset $Y$ of $X$, where $Y$ has size 5. Define the events

• A = "1 is an element of $Y$",
• B = "7 is an element of $Y$".

What is $\Pr(A|B)$?

13 . We flip a fair coin, independently, five times. Define the events

• A = "the coin comes up heads exactly four times",
• B = "the fifth coin flip results in heads".

What is $\Pr(A|B)$?

14 . Let $n \geq 3$ be an integer. Consider a uniformly random permutation $a_1a_2 \dots a_n$ of the set $\{1,2,\dots,n\}$. Define the events

• A = "$a_n = n$",
• B = "$a_2 > a_1$".

Which of the following is true?

15 . Let $n \geq 5$ be an integer. Consider a uniformly random permutation $a_1a_2 \dots a_n$ of the set $\{1,2,\dots,n\}$. Define the events

• A = "$a_1 = 1$",
• B = "$a_n = 5$".

What is $\Pr(A \cup B)$?

16 . Let $A$ and $B$ be two events in some sample space. You are given that $$ \begin{align} \Pr(A|B) &= \Pr(B|A), \\ \Pr(A \cup B) &= 1, \\ \Pr(A \cap B) &> 0. \end{align} $$ Which of the following is true?

17 . Consider a uniformly random permutation of the set $\{1,2,\dots,50\}$. Define the event

• A = "in the permutation, both 8 and 4 are to the left of both 1 and 2".

What is $\Pr(A)$?

18 . You roll a fair red die and a fair blue die, independently of each other. Define the random variables

• X = "the result of the red die",
• Y = "the result of the blue die",
• Z = $\min(X,Y)$.

What is $\Pr(Z = 2)$?

19 . Let $n \geq 3$ be an integer and consider a group $P_1,P_2,\dots,P_n$ of $n$ people. Each of these people has a uniformly random birthday, which is independent of the birthdays of the other people. We ignore leap years; thus, the year has 365 days.
Define the random variable $X$ to be the number of unordered triples $\{P_i,P_j,P_k\}$ of people (i.e., subsets consisting of three people) that have the same birthday.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.

20 . Consider a coin that comes up heads with probability 1/5 and comes up tails with probability 4/5. You flip this coin twice, independently of each other. For each heads, you win \$100. For each tails, you win \$50.
What is the expected value $\mathbb{E}(X)$ of $X$?

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 = \max(i, j). $$ Which of the following is true?

22 . Consider the following recursive algorithm $\TwoTails$, which takes as input a positive integer $k$: You run algorithm $\TwoTails(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm.
Let $m \geq 1$ be an integer. What is $\Pr(X = 2^m)$?

23 . Is the following statement true or false?

For any two random variables $X$ and $Y$, $\mathbb{E}(X \cdot Y) = \mathbb{E}(X) \cdot \mathbb{E}(Y)$.

24 . Elisa Kazan has successfully completed her first term as President of the Carleton Computer Science Society. In order to celebrate this, Elisa decides to spend an evening in the Hyacintho Cactus Bar and Grill in downtown Ottawa. During this evening, Tan Tran is working as a server. Since Tan has been studying very hard for COMP 2804, he is a bit absent-minded: Every time a customer orders a drink, Tan serves the wrong drink with probability 1/12, independently of other orders.
Elisa orders 7 ciders, one cider at a time. Let $(D_1,D_2,\dots,D_7)$ be the sequence of drinks that Tan serves. Define the following random variable $X$:

• X = the number of indices $i$ such that $D_i$ is a cider and $D_{i+1}$ is not a cider.

What is the expected value $\mathbb{E}(X)$ of $X$?

25 . How do you feel about writing an exam on Sunday afternoon?