Evaluation: 2014 Winter Final
1 .
A password consists of 28 characters, each character being a lowercase letter. A password must
contain exactly one vowel (i.e., a, e, i, o, or u).
How many passwords are there?
(a)
$28 \cdot 5 \cdot 21^{27}$
(b)
$5 \cdot 21^{27}$
(c)
$28 \cdot 5 \cdot 27^{21}$
(d)
$28 \cdot 5 \cdot 26^{27}$
2 .
A password consists of 10 characters, each character being a lowercase letter or a digit. A password
must contain at least one digit and at most three digits. How many passwords are there?
(a)
$10 \cdot 26^9 + 10^2 \cdot 26^8 + 10^3 \cdot 26^7$
(b)
${10 \choose 1} \cdot 10 \cdot 26^9 + {10 \choose 2} \cdot 10^2 \cdot 26^8 +$ $ {10 \choose 3} \cdot 10^3 \cdot 26^7$
(c)
${10 \choose 1}26^9 + {10 \choose 2}26^8 + {10 \choose 3}26^7$
(d)
none of the above
3 .
What is
$$
\sum_{k=0}^{45} {45 \choose k} (-3)^{2k}.
$$
(a)
$(-8)^{45}$
(b)
$4^{45}$
(c)
$(-2)^{45}$
(d)
$10^{45}$
4 .
Consider a group of 8 people, consisting of Simon, John, and 6 other people. How many ways are there
to arrange these 8 people on a horizontal line such that Simon and John are standing next to each
other? (The order on the line matters and Simon is either to the left or to the right of John.)
(a)
$2 \cdot 8 \cdot 6!$
(b)
$8 \cdot 6!$
(c)
$7 \cdot 6!$
(d)
$2 \cdot 7 \cdot 6!$
5 .
Consider strings consisting of $n$ characters, each character being $a$, $b$, or $c$. Let $S_n$ be the
number of such strings of length $n$ that do not contain the substring $aa$. Which of the following
is true?
(a)
$S_{n+1} = 2 \cdot S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$
(b)
$S_{n+1} = S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$
(c)
$S_{n+1} = 2 \cdot S_n + 2 \cdot S_{n-1}\ \mathrm{for}\ n \geq 2.$
(d)
$S_{n+1} = S_n + S_{n-1}\ \mathrm{for}\ n \geq 2.$
6 .
In a group of 150 people,
- 30 weigh at least 150 pounds,
- 60 are at least 6 feet tall,
- 70 weigh less than 150 pounds and are less than 6 feet tall.
(a)
10
(b)
30
(c)
20
(d)
40
7 .
Consider 4 blue balls $B_1,B_2,B_3,B_4$ and 5 red balls $R_1,R_2,R_3,R_4,R_5$. We pick 3
balls of the same color and arrange them on a horizontal line. (The order on the line matters.) How
many arrangements are there?
(a)
94
(b)
84
(c)
64
(d)
74
8 .
Consider a group of $n$ people, let $k$ be an integer with $1 \leq k \leq n$, and consider a
circular table with $k$ chairs around it. We select $k$ people and seat them around this table. How
many different seating arrangements are there? (Two seating arrangements $A$ and $B$ are the same if
for each person, the clockwise neighbor in $A$ is the same as the clockwise neighbor in $B$, and the
counterclockwise neighbor in $A$ is the same as the counterclockwise neighbor in $B$.)
(a)
$\frac{n!}{k(n-k)!}$
(b)
$\frac{n!}{k!(n-k)!}$
(c)
$\frac{2 \cdot n!}{(n-k)!}$
(d)
$\frac{n!}{(n-k)!}$
9 .
How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 777$, where $x_1 \geq 0$, $x_2 \geq 0$,
$x_3 \geq 0$, $x_4 \geq 0$ are integers?
(a)
${781 \choose 4}$
(b)
${781 \choose 3}$
(c)
${780 \choose 4}$
(d)
${780 \choose 3}$
10 .
Consider the following recursive function:
Which of the following is true?
| $f(0)$ | $\;=\;$ | $3,$ |
| $f(n + 1)$ | $\;=\;$ | $f(n) + 10n + 2\; \ \text{for all}$ $\text{integers}\ n \geq 0.$ |
(a)
for all $n \geq 0$: $f(n) = 5n^{2} - 3n + 3$
(b)
for all $n \geq 0$: $f(n) = 5n^{2} - 2n + 3$
(c)
for all $n \geq 0$: $f(n) = 5n^{2} + 3n + 3$
(d)
for all $n \geq 0$: $f(n) = 5n^{2} - 3n + 2$
11 .
Consider the recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:
Which of the following is true?
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for
$n \geq 2$. 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$
Which of the following is true?
(a)
for all $n \geq 5$, $a_n = f_{n-1}$
(b)
for all $n \geq 5$, $a_n = f_{n-3}$
(c)
for all $n \geq 5$, $a_n = f_n$
(d)
for all $n \geq 5$, $a_n = f_{n-2}$
12 .
We choose a subset of $\{1,2,3,4,5\}$ uniformly at random. What is the probability that this
subset has size 3?
(a)
4/32
(b)
5/32
(c)
5/16
(d)
4/16
13 .
Let $A = \{1,2,3,\dots,100\}$. Let $x$, $y$, and $z$ be elements in $A$ that are chosen independently
and uniformly at random. What is the probability that $x = y = z$?
(a)
$\frac{1}{100 \cdot 100}$
(b)
$\frac{1}{100 \cdot 99}$
(c)
$\frac{1}{100}$
(d)
$\frac{1}{{100 \choose 2}}$
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 $H$ or $TTTT$. What is the
probability that this sequence contains at most two $T$s?
(a)
4/8
(b)
5/8
(c)
7/8
(d)
6/8
15 .
We roll two fair and independent dice. Define the events
- A = "at least one of the dice shows a 3",
- B = "the sum of the dice is 5".
(a)
1/2
(b)
1/8
(c)
1/9
(d)
1/4
16 .
Let $C_1$ be a fair coin that has $H$ on one side and $T$ on the other side. Let $C_2$ be a coin
that has $H$ on both sides. We choose one of $C_1$ and $C_2$ uniformly at random and flip it. Define
the events
- A = "we choose $C_2$",
- B = "the flip resulted in $H$".
(a)
none of the above
(b)
1/3
(c)
1/2
(d)
2/3
17 .
Let $A$ and $B$ be events in a sample space, such that $\Pr(A) = 1/3$, $\Pr(B) = 1/2$,
and $\Pr(A|B) = 2/5$. What is $\Pr(B|A)$?
(a)
4/5
(b)
1/5
(c)
3/5
(d)
2/5
18 .
Consider a group of 5 people. Each person in this group was born in a uniformly random month (from
the 12 months of the year), independent of the other people's month of birth. What is the
probability that at least 2 of these 5 people were born in the same month?
(a)
$1 - \frac{11!}{12^{4} \cdot 8!}$
(b)
$1 - \frac{12!}{12^{4} \cdot 7!}$
(c)
$1 - \frac{11!}{12^{4} \cdot 6!}$
(d)
$1 - \frac{11!}{12^{4} \cdot 7!}$
19 .
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} \cdot \frac{1}{3} + \frac{3}{4} \cdot \frac{1}{4}$
(b)
none of the above
(c)
$\frac{1}{3}$
(d)
$\frac{1}{4}$
20 .
I flip two fair and independent coins. If the first coin comes up heads, you win \$1.
If the second coin comes up heads, you win \$2. (Thus, if both coins come up heads, you win \$3.)
Define the random variable $X$ to be the amount of dollars that you win. What is the expected
value of $X$?
(a)
2
(b)
3
(c)
5/2
(d)
3/2
21 .
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 2 girls or 2 boys. Define the random variables
- G = the number of girls the couple has
- B = the number of boys the couple has.
(a)
No
(b)
Yes
22 .
I flip a fair coin, independently, 10 times, resulting in a sequence of heads ($H$) and tails ($T$).
For each $HT$ in this sequence, you win \$3.
Define the random variable $X$ to be the amount of dollars that you win. For example, if the
sequence is
$$
HHTTHTTHTT,
$$
then $X = 9$. What is the expected value of $X$?
(a)
30/4
(b)
29/4
(c)
27/4
(d)
28/4
23 .
We roll a pair of fair dice repeatedly and independently, and stop as soon as the sum of the numbers
for the pair is 7. Define the random variable $X$ to be the number of times we roll the dice. (In
one roll, we roll a pair of dice.) What is the expected value of $X$?
(a)
5
(b)
7
(c)
4
(d)
6
24 .
We flip a fair coin independently $n$ times. Define the random variable
- X = the number of heads minus the number of tails in the sequence of $n$ flips.
(a)
$n/4$
(b)
$n/2$
(c)
$0$
(d)
$n/8$