Evaluation: 2022 Winter Final
1 . Consider strings of length $70$, in which each character is one of the characters $a,b,c,d,e$. How many such strings have exactly $10$ letters $e$?
(a)
$\binom{70}{10}\cdot 4^{60}$
(b)
$\binom{70}{5}\cdot 5^{60}$
(c)
$\binom{70}{10}\cdot 5^{60}$
(d)
$\binom{70}{5}\cdot 4^{60}$
(e)
$5^{10}\cdot 4^{60}$
2 . Consider strings of length $70$, in which each character is one of the characters $a,b,c,d,e$. How many such strings have exactly $5$ letters $a$ and exactly $15$ letters $b$?
(a)
$\binom{70}{5}\cdot\binom{70}{15}\cdot 3^{50}$
(b)
$\binom{70}{5}\cdot\binom{65}{15}\cdot 5^{50}$
(c)
$\binom{70}{5}\cdot\binom{65}{15}\cdot 3^{50}$
(d)
$\binom{70}{15}\cdot\binom{55}{5}\cdot 5^{50}$
(e)
$\binom{70}{5}\cdot\binom{65}{15}\cdot 4^{50}$
3 . Consider strings of length $70$, in which each character is one of the characters $a,b,c,d,e$. How many such strings have exactly $5$ letters $a$ or exactly $15$ letters $b$?
(a)
$\binom{70}{5}\cdot 4^{65} + \binom{70}{15}\cdot 4^{55}$
(b)
None of the above
(c)
$\binom{70}{5}\cdot 4^{65} + \binom{65}{15}\cdot 4^{50} $
(d)
$\binom{70}{5}\cdot 4^{65} + \binom{70}{15}\cdot 4^{55} - \binom{70}{5}\cdot\binom{65}{15}\cdot 3^{50}$
(e)
$\binom{70}{5}\cdot 4^{65} + \binom{65}{15}\cdot 4^{50} - \binom{70}{5}\cdot\binom{65}{15}\cdot 3^{50}$
4 . Consider strings of length $70$, in which each character is one of the characters $a,b,c,d,e$. How many such strings have at least $10$ letters $a$?
(a)
$\binom{70}{10}\cdot 5^{60}$
(b)
None of the above
(c)
$\binom{70}{10}\cdot 4^{60}$
(d)
$5^{70} - \sum_{i=0}^{9} \binom{70}{i}\cdot 4^{70-i}$
(e)
$\sum_{i=10}^{70} \binom{70}{i}\cdot 5^{70-i}$
5 . Let $S$ be a set of $m+w$ people, $m\ge 10$ of which are men and $w\ge 10$ of which are women. What does
\[
\sum_{k=2}^{10} \binom{m}{m-k}\cdot\binom{w}{10-k}
\]
count?
(a)
The number subsets of $S$ of size at most $10$ that include at least $2$ men?
(b)
The number $10$-element subsets of $S$ that include at least $2$ men?
(c)
The number subsets of $S$ of size at most $10$ that include at least $2$ women?
(d)
None of the Above
(e)
The number $10$-element subsets of $S$ that include at least $2$ women?
6 . What is the coefficient of $x^{10}y^{20}$ in the expansion of $(2x - 3y)^{30}$?
(a)
$\binom{30}{20}\cdot 2^{20}\cdot 3^{10}$
(b)
$\binom{30}{20}\cdot 2^{30}\cdot 3^{10}$
(c)
$\binom{30}{20}\cdot 2^{10}\cdot 3^{20}$
(d)
$-\binom{30}{10}\cdot 2^{20}\cdot 3^{10}$
(e)
$\binom{30}{10}\cdot 2^{20}\cdot 3^{10}$
7 . A string that is obtained by rearranging the letters of the word
\[
\mathrm{ARABICA}
\]
is stupendous if it contains the substring $\mathrm{CAB}$. For example $\mathrm{ARA\underline{CAB}I}$ and $\mathrm{I\underline{CAB}AAR}$ are both stupendous, but $\mathrm{ARABICA}$ is not. How many stupendous strings are there?
(a)
$50$
(b)
$30$
(c)
$40$
(d)
$60$
(e)
$70$
8 . Let $n\ge 1$ be an integer and let $S_n$ be the number of ways in which $n$ can be written as a sum of $1$'s and $3$'s, in which the order of the terms matters. For example, $S_4=3$ because
\[ 4 = 1+1+1+1 = 1+3 = 3+1 \enspace . \]
Which of the following is true, for any integer $n\ge 4$:
(a)
$S_n=S_{n-1}+S_{n-2}$
(b)
$S_n=3S_{n-1}$
(c)
$S_n=S_{n-1}+S_{n-3}$
(d)
$S_n=S_{n-1}+S_{n-2}+S_{n-3}$
(e)
$S_n=3S_{n-3}$
9 . For each integer $n\ge 0$, let $S_n$ denote the number of length-$n$ strings over the alphabet $ \{a,b,c\} $ that do not contain $aa$ or $bb$.
Which of the following is true, for any integer $n\ge 1$?
(a)
$S_n=S_{n-1} + 4S_{n-2}$
(b)
$S_n=S_{n-1} + \sum_{i=1}^{n} 2S_{n-i}$
(c)
$S_n=S_{n-1} + 2S_{n-2}$
(d)
$S_n=S_{n-1} + \sum_{i=0}^{n-2} S_{i}$
(e)
$S_n=S_{n-1} + \sum_{i=0}^{n-2} 2S_{i}$
10 . The function $ T: \mathbb{N} \rightarrow \mathbb{N} $ is defined recursively as follows:
\[
T(n) =
\begin{cases}
3 & \text{if $n=0$} \\
2\cdot T(n-1) + 3 & \text{if $n\ge 1$}
\end{cases}
\]
Which of the following is true, for all $n\ge 0$?
(a)
$T(n)= 3^{n+1}$
(b)
$T(n)= 2^{n+1}+1$
(c)
$T(n)=2(3^{n+1}-1)$
(d)
$T(n)= 3n$
(e)
$T(n)=3(2^{n+1}-1)$
11 . Let $D$ be the result of rolling a normal $6$-sided die. What is $\Pr(D\bmod 4 = 0)$?
(a)
$1/2$
(b)
$1/5$
(c)
$1/3$
(d)
$1/4$
(e)
$1/6$
12 . Let $D_1$ and $D_2$ be the results of rolling two normal $6$-sided dice. What is $\Pr((D_1+D_2)\bmod 4 = 0)$?
(a)
$1/6$
(b)
$1/2$
(c)
$1/4$
(d)
$1/5$
(e)
$1/3$
13 . Let $D_1,\ldots,D_5$ be the results of rolling five normal $6$-sided dice and let $X=D_1+D_2+D_3+D_4+D_5$. What is $\Pr(X\bmod 4 = 0)$?
(a)
$1/5$
(b)
$1/3$
(c)
$1/2$
(d)
$1/4$
(e)
$1/6$
14 . Let $D_1,\ldots,D_{2n}$ be the result of rolling a $6$-sided die $2n$ times, and consider the length-$n$ sequence
\[ S=\langle (D_1+D_2), (D_3+D_4), (D_5+D_6),\ldots, (D_{2n-1}+D_n)\rangle \]
whose entries are all in the set $\{2,3,\ldots,12\}$. Let $k$ be an integer in $\{0,\ldots,n\}$. What is the probability that $S$ contains exactly $k$ many $5$'s?
(a)
$\binom{n}{k}\cdot(\tfrac{1}{5})^k\cdot (\tfrac{4}{5})^{n-k}$
(b)
$\binom{n}{k}\cdot(\tfrac{1}{36})^k\cdot (\tfrac{35}{36})^{n-k}$
(c)
$\binom{n}{k}\cdot(\tfrac{1}{11})^k\cdot (\tfrac{10}{11})^{n-k}$
(d)
$\binom{n}{k}\cdot(\tfrac{1}{12})^k\cdot (\tfrac{11}{12})^{n-k}$
(e)
$\binom{n}{k}\cdot(\tfrac{1}{9})^k\cdot (\tfrac{8}{9})^{n-k}$
15 . Let $\pi_1,\ldots,\pi_{20}$ be a random permutation of $\{1,\ldots,20\}$. Define the events:
$ A = \pi_{10}>\pi_{11} $
and
$ B = \pi_{11} \gt \pi_{12} $
Which of the following is true?
(a)
$\Pr(A\cap B) = \Pr(A)\cdot\Pr(B)$
(b)
$\Pr(A\cap B) < \Pr(A)\cdot\Pr(B)$
(c)
$\Pr(A\cap B) > \Pr(A)\cdot\Pr(B)$
(d)
$\Pr(A\mid B)$ is undefined
(e)
None of the above
16 . Let $D_1,D_2,D_3$ be the result of rolling a normal $6$-sided die three times. Define the events
- $A = \max\{D_1,D_2,D_3\}=4$
- $B = D_1+D_2+D_3$ is an even number
(a)
All of the above
(b)
$\Pr(A\mid B)$ is undefined
(c)
None of the above
(d)
$A$ and $B$ are independent
(e)
$A$ and $B$ are not independent
17 . Let $A$ and $B$ be two independent events in some probability space. You are told that $\Pr(A)=1/3$ and that $\Pr(B)=1/2$. What is $\Pr(A\cup B)$?
(a)
$1/2$
(b)
$1/4$
(c)
$1/3$
(d)
$2/3$
(e)
$3/4$
18 . Let $X$ and $Y$ be the results of rolling two $4$-sided dice and let $Z=\max\{X,Y\}$. What is $ E(Z)$?
(a)
$3$
(b)
$13/4=3.25$
(c)
$25/8=3.125$
(d)
$7/2=3.5$
(e)
$5/2=2.5$
19 . A group of $n\ge 3$ friends stand around in a circle and each friend tosses a coin. If the result of a friend's coin toss is the different from the result of the coin tossed by their left neighbour and different from result of the coin tossed by their right neighbour, then the friend shouts Huzzah! Let $X$ be the number of friends who shout Huzzah!. What is $ E(X)$?
(a)
$n/8$
(b)
$n/4$
(c)
$n/3$
(d)
$n/2$
(e)
None of the above
20 . Let $X_1,X_2,X_3$ be three numbers chosen independently and uniformly from the set $\{1,\ldots,50\}$. Let $Z=\max\{X_1,X_3,X_4\}$. What is $ E(Z) $?
(a)
$99/2-49.5$
(b)
$50^{-3}\cdot\sum_{i=1}^{50} i\cdot (3(i-1)^2 + 3(i-1) + 1)$
(c)
$33$
(d)
$50^{-3}\cdot\sum_{i=1}^{50} i\cdot i^3$
(e)
$50^{-3}\cdot\sum_{i=1}^{50} i\cdot i^2$
21 . Let $D_1$ and $D_2$ be the result of tossing a $6$-sided die twice. Define the random variables
\[ X=\max\{D_1,D_2\} \]
and
\[ Y=D_1+D_2 \enspace . \]
Which of the following is true?
(a)
$X$ and $Y$ are independent
(b)
None of the above
(c)
$X$ and $Y$ are not independent
22 . Let $D_1$ and $D_2$ be the result of tossing a $6$-sided die twice. Define the random variables
\[ X=2\cdot D_1 \]
and
\[ Y=
\begin{cases}
1 & \text{if $D_1+D_2=7$} \\
0 & \text{otherwise.} \enspace .
\end{cases}
\]
Which of the following is true?
(a)
None of the above
(b)
$X$ and $Y$ are not independent
(c)
$X$ and $Y$ are independent
23 . Is the following statement true or false?
For any random variable $X$, $\mathbb{E}(X^2) = \mathbb{E}(X)\cdot \mathbb{E}(X)$.
(a)
The statement is false
(b)
The statement is neither true nor false
(c)
The statement is true
24 . Let $n\ge 2$ be an integer and let $x_1,\ldots,x_n$ be a random permutation of $\{1,\ldots,n\}$. Define the random variable
\[ I=\min\left(\{n+1\}\cup\{i\ge 2:x_i > x_1\}\right) \enspace .
\]
What is $ E(I)$?
(a)
$n/2$
(b)
$H_n$
(c)
$H_{n+1}$
(d)
$H_{n-1}$
(e)
$3$