Evaluation: 2014 Fall Final
1 .
A password consists of 13 characters, each character being one of the ten digits $0,1,2,\dots,9$.
A password must contain exactly one odd digit. How many passwords are there?
A password must contain exactly one odd digit. How many passwords are there?
(a)
$13 \cdot 5^{13}$
(b)
$13 \cdot 9^{12}$
(c)
$13 \cdot 5^{12}$
(d)
$13 \cdot 5 \cdot 9^{12}$
2 .
A password consists of 13 characters, each character being one of the ten digits $0,1,2,\dots,9$.
A password must contain at least one odd digit and at most two even digits. How many passwords are there?
A password must contain at least one odd digit and at most two even digits. How many passwords are there?
(a)
$5 \cdot 9^{12} + 13 \cdot 5 \cdot 9^{12} + {13 \choose 2}5 \cdot 9^{12}$
(b)
$5^{13} + 13 \cdot 5^{13} + {13 \choose 2}5^{13}$
(c)
$5^{12} + 13 \cdot 5^{12} + {13 \choose 2}5^{12}$
(d)
$5^{13} + 13 \cdot 9^{12} + {13 \choose 2}9^{12}$
3 .
What is
$$
\sum_{k = 0}^{45} {45 \choose k}(-3)^{2k}.
$$
(a)
$(-8)^{45}$
(b)
$(-2)^{45}$
(c)
$4^{45}$
(d)
$10^{45}$
4 .
How many bitstings of length 13 start with 010 or end with 11?
(a)
$2^{10} + 2^{11}$
(b)
None of the above.
(c)
$2^{13} - (2^{10} + 2^{11})$
(d)
$3 \cdot 2^{10} - 2^{8}$
5 .
Let $S_n$ be the number of bitstrings of length $n$ that do not contain the substring 11. Which of
the following is true?
(a)
$S_n = S_{n-1} + S_{n-3}\ \mathrm{for}\ n \geq 3.$
(b)
$S_n = 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 3.$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}\ \mathrm{for}\ n \geq 3.$
(d)
$S_n = S_{n-1} + S_{n-2}\ \mathrm{for}\ n \geq 3.$
6 .
In a group of 100 students,
- 40 like 8:30am classes,
- 30 like the course COMP 2804,
- 50 do not like 8:30am classes and do not like the course COMP 2804.
(a)
20
(b)
40
(c)
30
(d)
10
7 .
Consider $m \geq 7$ blue balls $B_1,B_2,\dots,B_m$ and $n \geq 7$ red balls $R_1,R_2,\dots,R_n$.
We pick 7 balls of the same color and arrange them on a horizontal line. (The order on the line
matters.) How many arrangements are there?
(a)
$7!{m + n \choose 7}$
(b)
None of the above.
(c)
$m!{m \choose 7} + n!{n \choose 7}$
(d)
$7!{m \choose 7} + 7!{n \choose 7}$
8 .
The number of different strings that can be made by reordering the 10 letters of the word AAABBCCCCC is
(a)
None of the above.
(b)
${10 \choose 3}{10 \choose 2}{10 \choose 5}$
(c)
$10!$
(d)
$\frac{10!}{2!3!5!}$
9 .
How many solutions are there to the equation $x_1 + x_2 + x_3 = 13$, where $x_1 \geq 0$, $x_2 \geq 0$,
$x_3 \geq 0$ are integers?
(a)
${14 \choose 2}$
(b)
${13 \choose 2}$
(c)
${15 \choose 2}$
(d)
${16 \choose 2}$
10 .
Consider the following recursive function:
Which of the following is true?
| $f(0) = $ | $-17,$ |
| $f(n) = $ | $f(n - 1) + 8n - 2\; \ \text{for all}$ $\text{integers}\ n \geq 1.$ |
(a)
for all $n \geq 0$: $f(n) = 4n^{2} - 2n - 17$
(b)
for all $n \geq 0$: $f(n) = 3n^{2} + n - 17$
(c)
for all $n \geq 0$: $f(n) = 3n^{2} - n - 17$
(d)
for all $n \geq 0$: $f(n) = 4n^{2} + 2n - 17$
11 .
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
Consider the recursive algorithm $\Fib$, which takes as input an
integer $n \geq 0$:
$\mathbf{Algorithm}\ \Fib(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ f = n$
$\mathbf{else}\ f = \Fib(n - 1) + \Fib(n - 2)$
$\mathbf{endif};$
$\mathbf{return}\ f$
(a)
4
(b)
7
(c)
6
(d)
5
12 .
A bowl contains 5 blue balls, 4 red balls, and 6 green balls. We choose 2 balls uniformly at random.
What is the probability that these 2 balls have the same color?
(a)
$\frac{{5 \choose 2}{4 \choose 2}{6 \choose 2}}{{15 \choose 2}}$
(b)
$\frac{{15 \choose 2}}{{5 \choose 2} + {4 \choose 2} + {6 \choose 2}}$
(c)
$\frac{{15 \choose 2}}{{5 \choose 2}{4 \choose 2}{6 \choose 2}}$
(d)
$\frac{{5 \choose 2} + {4 \choose 2} + {6 \choose 2}}{{15 \choose 2}}$
13 .
Annie, Boris, and Charlie have random and independent birthdays. (We ignore leap years, so that a
year has 365 days.) What is the probability that Annie, Boris, and Charlie have the same birthday?
(a)
$\frac{1}{364 \cdot 365}$
(b)
$\frac{1}{365^2}$
(c)
$\frac{365}{364^{2}}$
(d)
$\frac{1}{365^{3}}$
14 .
We flip a fair coin repeatedly and independently, resulting in a sequence of heads ($H$) and tails
($T$). We stop flipping the coin as soon as this sequence contains one $H$ or eight $T$s. What is
the probability that this sequence contains at most 7 $T$s?
(a)
$1 - (1/2)^{7}$
(b)
None of the above.
(c)
$\sum_{k=0}^{7} (1/2)^{k}$
(d)
$\sum_{k=0}^{7} (1/2)^{k+1}$
15 .
A bowl contains 5 blue balls and 4 red balls. We choose 2 balls uniformly at random. Define the
events
- A = "both balls are red",
- B = "both balls have the same color".
(a)
$\frac{{4 \choose 2}}{{5 \choose 2}{4 \choose 2}}$
(b)
$\frac{{4 \choose 2}}{{9 \choose 2}}$
(c)
$\frac{{5 \choose 2} + {4 \choose 2}}{{4 \choose 2}}$
(d)
$\frac{{4 \choose 2}}{{5 \choose 2} + {4 \choose 2}}$
16 .
We choose an element $x$ uniformly at random from the set $\{1,2,3,\dots,10\}$. Define the events
- A = "$x$ is even",
- B = "$x$ is divisible by 3".
(a)
3/10
(b)
1/3
(c)
1/2
(d)
2/3
17 .
We choose an element $x$ uniformly at random from the set $\{1,2,3,\dots,10\}$. Define the events
- A = "$x$ is even"
- B = "$1 \leq x \leq 5$".
(a)
The events $A$ and $B$ are not independent.
(b)
None of the above.
(c)
The events $A$ and $B$ are independent.
18 .
We choose an element $x$ uniformly at random from the set $\{1,2,3,\dots,10\}$. Define the events
- A = "$x$ is even"
- B = "$1 \leq x \leq 6$".
(a)
The events $A$ and $B$ are independent.
(b)
The events $A$ and $B$ are not independent.
(c)
None of the above.
19 .
When a couple has a child, this child is a boy with probability 1/2 and a girl with probability
1/2, independent of the gender of previous children. A couple stops having children as soon as
they have a child that has the same gender as their first child. Define the events
- A = "the second child is a boy"
- B = "the couple has at least three children and the third child is a boy".
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
20 .
Assume you answer the first question in this exam by choosing one of the four answers uniformly at random.
You answer the second question by choosing, again uniformly at random, one of the three answers you did not choose in
the first question. What is the probability that you answer the second question correctly?
(a)
$\frac{1}{4}$
(b)
$\frac{1}{3}$
(c)
None of the above.
(d)
$\frac{1}{4} \cdot \frac{1}{3} + \frac{3}{4} \cdot \frac{1}{4}$
21 .
I flip two fair and independent coins. If the first coin comes up tails, you lose \$1 (i.e., you win -\$1).
If the second coin comes up heads, you win \$2. (Thus, if the first coin comes up tails and the second coin
comes up heads, you win \$1.) Define the random variable $X$ to be the amount of dollars that you win.
What is the expected value of $X$?
(a)
1/4
(b)
1
(c)
2
(d)
1/2
22 .
I flip a fair coin, independently, 6 times, resulting in a sequence of heads ($H$) and tails ($T$).
For each (consecutive) $HTH$ in this sequence, you win \$5.
Define the random variable $X$ to be the amount of dollars that you win. For example, if the
sequence is
$$
THTHTH,
$$
then $X = 10$. What is the expected value of $X$?
(a)
5
(b)
2/5
(c)
5/2
(d)
2
23 .
$\newcommand{\ThreeHeadsOrThreeTails}{{\rm T {\scriptsize HREE} H {\scriptsize EADS} O {\scriptsize R} T {\scriptsize HREE} T {\scriptsize AILS}}}$
Consider the following recursive algorithm $\ThreeHeadsOrThreeTails$, which takes as input a positive integer $k$:
$\mathbf{Algorithm}$ $\ThreeHeadsOrThreeTails(k)$:
$\quad \text{flip a fair coin three times};$
$\quad \mathbf{if}\ \text{the result is $HHH$ or $TTT$}$
$\quad \quad \mathbf{then}\ \mathrm{return}\ k$
$\quad \mathbf{else}$
$\quad \quad \ThreeHeadsOrThreeTails(k + 1)$
$\quad \mathbf{endif}$
(a)
4
(b)
5
(c)
3
(d)
2
24 .
We flip a fair coin independently $n$ times. Define the random variable
- X = twice the number of heads minus three times the number of tails.
(a)
$-n$
(b)
$n$
(c)
$-n/2$
(d)
$n/2$