Evaluation: 2016 Fall Final
1 .
Consider a set $A$ having size 7 and a set $B$ having size 9. How many functions $f : A \rightarrow B$
are there?
(a)
$9^7$
(b)
$7^9$
(c)
$9!$
(d)
$7!$
2 .
Consider a set $A$ having size 7 and a set $B$ having size 9. How many one-to-one functions
$f : A \rightarrow B$ are there?
(a)
$\frac{9!}{2}$
(b)
$\frac{7!}{2}$
(c)
$\frac{7!}{3}$
(d)
$\frac{9!}{3}$
3 .
How many bitstrings of length 55 start with 000 or end with 1010?
(a)
$2^{51} + 2^{52} - 2^{48}$
(b)
$2^{55} - 2^{48}$
(c)
$2^{51} + 2^{52}$
(d)
None of the above.
4 .
What does $2^{n} - 1 - n - {n \choose 2}$ count?
(a)
The number of subsets of a set of size $n$ that have size at least two.
(b)
The number of subsets of a set of size $n$ that have size at least three.
(c)
The number of bitstrings of length $n$ that have at least two 1's.
(d)
The number of bitstrings of length $n$ that have at most two 1's.
5 .
In a group of 100 students,
- 25 drink cider,
- 50 drink beer,
- 33 do not drink cider and do not drink beer.
(a)
10
(b)
9
(c)
11
(d)
8
6 .
Consider strings of characters, each character being $a$ or $b$, that contain at least one
occurrence of $aa$. Let $S_n$ be the number of such strings having length $n$. Which of the
following is true for $n \geq 4$?
(a)
$S_n = S_{n-1} + S_{n-2} + 2^{n-2}$
(b)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(c)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$
(d)
$S_n = S_{n-1} + 2 \cdot S_{n-2}$
7 .
Consider strings of characters, each character being $a$ or $b$, that contain exactly two $a$'s and
these two $a$'s are not next to each other. Let $S_n$ be the number of such strings having length
$n$. Which of the following is true for $n \geq 4$?
(a)
$S_n = {n \choose 2} - n + 1$
(b)
$S_n = {n \choose 2} - n$
(c)
$S_n = {n \choose 2}$
(d)
$S_n = {n \choose 2} - n - 1$
8 .
Consider the following recursive function:
- f(0) = $1$,
- f(n) = $\frac{5}{n} \cdot f(n - 1)\; \ \text{for all}$ $\mathrm{integers}\ n \geq 1$.
(a)
$f(n) = \frac{5^{n}}{(n+1)!}$
(b)
$f(n) = \frac{5}{n!}$
(c)
$f(n) = \frac{5^{n+1}}{n!}$
(d)
$f(n) = \frac{5^{n}}{n!}$
9 .
$\newcommand{\Hello}{{\rm H {\scriptsize ELLO}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the recursive algorithm $\Hello$, which takes as input an integer $n \geq 0$:
If we run algorithm $\Hello(7)$, how many times is the word "hello" printed?
(a)
6
(b)
4
(c)
7
(d)
5
10 .
Consider strings of characters, each character being $a$, $b$, $c$, $d$, or $e$, in which no two
consecutive characters are equal. Let $S_n$ be the number of such strings having length $n$. Which
of the following is true for $n \geq 1$?
(a)
$S_n = 5 \cdot 4^{n-1}$
(b)
$S_n = 5^{n} - 5(n-1) \cdot 4^{n-1}$
(c)
$S_n = 5 \cdot 4^{n-2}$
(d)
$S_n = 5^{n} - 5(n-1) \cdot 4^{n-2}$
11 .
How many solutions are there to the equation
$$
x_1 + x_2 + x_3 + x_4 + x_5 = 28,
$$
where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$, and
$x_5 \geq 0$ are integers?
(a)
${33 \choose 4}$
(b)
${32 \choose 5}$
(c)
${32 \choose 4}$
(d)
${33 \choose 5}$
12 .
You roll a fair red die and a fair blue die, independently of each other. Let $r$ be the result of
the red die and let $b$ be the result of the blue die. Define the events
- A = "$r + b = 6$",
- B = "$b = 4$".
(a)
1/5
(b)
1/3
(c)
1/4
(d)
1/6
13 .
Let $V$ be a set consisting of 12 even integers and 8 odd integers. We choose a uniformly random
subset $W$ of $V$ having size 7. Define the event
- A = "exactly 4 of the elements of $W$ are even".
(a)
$\frac{{12 \choose 4}+{8 \choose 3}}{20 \choose 7}$
(b)
$\frac{{12 \choose 4}{8 \choose 3}}{20 \choose 7}$
(c)
$\frac{{20 \choose 3}{17 \choose 4}}{20 \choose 7}$
(d)
$\frac{{20 \choose 4}{16 \choose 3}}{20 \choose 7}$
14 .
We flip a fair coin three times; these flips are independent of each other. These three coin flips
give us a sequence of length three, where each symbol is $H$ or $T$. Define the events (recall that
0 is even):
- A = "the number of $H$ in the sequence is even",
- B = "the sequence contains at least two consecutive $H$'s".
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
15 .
We flip a fair coin three times; these flips are independent of each other. These three coin flips
give us a sequence of length three, where each symbol is $H$ or $T$. Define the events
- A = "the sequence contains at most one $T$",
- B = "the symbols in the sequence are not all equal".
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
16 .
Let $n \geq 2$ be the number of students who are writing this exam. Each of these students has a
uniformly random birthday, which is independent of the birthdays of the other students. We ignore
leap years; thus, the year has 365 days. Define the event
- A = "at least two students have their birthday on December 14".
(a)
$1 - {n \choose 2} \cdot \left( \frac{1}{365} \right)^2 \cdot \left( \frac{364}{365} \right)^{n-2}$
(b)
${\sum_{k=2}^{n}} {n \choose k} \cdot \left( \frac{1}{365} \right)^k$
(c)
$1 - \left( \frac{364}{365} \right)^n - n \cdot \frac{1}{365} \cdot \left( \frac{364}{365} \right)^{n-1}$
(d)
${n \choose 2} \cdot \left( \frac{1}{365} \right)^2 \cdot \left( \frac{364}{365} \right)^{n-2}$
17 .
Let $X = \{1,2,\dots,100\}$. We choose a uniformly random subset $Y$ of $X$ having size 17. Define the event
- A = "$4 \in Y$ or $7 \in Y$".
(a)
$1 - \frac{{98}\choose{15}}{{100}\choose{17}}$
(b)
$\frac{2 \cdot {99 \choose 16} - {98 \choose 15}}{100 \choose 17}$
(c)
$\frac{2 \cdot {99 \choose 16}}{100 \choose 17}$
(d)
$1 - \frac{{100 \choose 2} \cdot {98 \choose 15}}{100 \choose 17}$
18 .
Consider a uniformly random permutation of the set $\{1,2,\dots,77\}$. Define the event
- A = "in the permutation, both 8 and 4 are to the left of 3".
(a)
1/2
(b)
1/4
(c)
1/3
(d)
None of the above.
19 .
Let $n \geq 2$ be an integer and let $a_1a_2 \dots a_n$ be a uniformly random permutation of the set
$\{1,2,\dots,n\}$. Let $X$ be the random variable with the value
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
- X = the number of indices $i$ with $1 \leq i \leq n - 1$ and $a_i < a_{i + 1}$.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
(a)
$\frac{n-1}{2}$
(b)
$\frac{n}{2}$
(c)
$\frac{n}{4}$
(d)
$\frac{n-1}{4}$
20 .
Let $n \geq 2$ 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 pairs $\{P_i,P_j\}$ of people that have the same birthday.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
Define the random variable $X$ to be the number of unordered pairs $\{P_i,P_j\}$ of people that have the same birthday.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
(a)
$\frac{1}{365} \cdot {n \choose 2}$
(b)
$\left( \frac{1}{365} \right)^2 \cdot {n \choose 2}$
(c)
$\left( \frac{1}{365} \right)^2 \cdot n^2$
(d)
$\frac{1}{365} \cdot n^2$
21 .
Consider a coin that comes up heads with probability 1/7 and comes up tails with probability 6/7.
You flip this coin once. If it comes up heads, you win \$5. If it comes up tails, you win \$2.
What is the expected value $\mathbb{E}(X)$ of $X$?
What is the expected value $\mathbb{E}(X)$ of $X$?
(a)
7/2
(b)
32/7
(c)
7/17
(d)
17/7
22 .
You flip a fair coin 7 times; these coin flips are independent of each other. Define the random
variables
- X = the number of heads in these 7 coin flips,
- Y = the number of tails in these 7 coin flips.
(a)
The random variables $X$ and $Y$ are not independent.
(b)
None of the above.
(c)
The random variables $X$ and $Y$ are independent.
23 .
Consider the set $S = \{1,2,3,...,10\}$. You choose a uniformly random element $z$ in $S$.
Define the random variables
$$
X =
\begin{cases}
0\; \ \text{if \(z\) is even}, \\
1\; \ \text{if \(z\) is odd}
\end{cases}
$$
and
$$
Y =
\begin{cases}
0\; \ \mathrm{if}\ z \in \{1,2\}, \\
1\; \ \mathrm{if}\ z \in \{3,4,5,6\}, \\
2\; \ \mathrm{if}\ z \in \{7,8,9,10\}.
\end{cases}
$$
Which of the following is true?
(a)
None of the above.
(b)
The random variables $X$ and $Y$ are not independent.
(c)
The random variables $X$ and $Y$ are independent.
24 .
You repeatedly and independently roll a fair die until the result of the roll is divisible by 3.
Define the random variable $X$ to be the number of times you roll the die. For example, if the
results of the rolls are 4, 5, 1, 4, 3, then $X=5$.
What is the expected value $\mathbb{E}(X)$ of $X$?
What is the expected value $\mathbb{E}(X)$ of $X$?
(a)
4
(b)
2
(c)
5
(d)
3