Can You Cheat on the Quiz?¶
Fiddler¶
Uh-oh, Charlie’s teacher is giving a pop quiz today! The quiz consists of three multiple choice questions, each with four choices (A, B, C, and D). Each correct answer is worth 1 point. Charlie didn’t study, and has absolutely no idea what the answers might be. That said, he still wants to maximize his score on the quiz.
Importantly, Charlie happens to know that his teacher is a little obsessive when it comes to creating quizzes. In particular, consecutive questions never have the same correct answer. For example, if the answer to one question is C, then the answer to the following question cannot be C.
Also Charlie is a bit of a, well, cheat. He glances over at the quiz of his neighbor, who definitely studied and knows the answer to every question. Charlie spots the correct answer to the first question on his neighbor’s quiz.
At this point, the neighbor carefully covers their quiz, meaning Charlie must rely on his own wits for the remaining two questions.
On average, what score can Charlie expect to earn on this quiz?
Induction Proof¶
I will solve a general solution first.
Note that with no conditional information, there are $4^q$ possible answer keys for $Q$ questions. Given one answer and that no consecutive answers are the same yields $3^{q-1}$ answer keys.
The solution will be explained in terms of the probability matrix at a question $q$ as
$$\begin{bmatrix}A_q \\ B_q \\ C_q \\ D_q\end{bmatrix}$$
and transition matrix
$$\begin{bmatrix}0 & \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & 0 & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & 0 & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} & 0 \end{bmatrix}$$
as any answer can not be the same as an adjacent question.
Assume, WLOG, that the answer to the question you look at is $A$.
For questions that are an even $p$ problems away from the question you look at, the probability matrix is
$$\boxed{\begin{bmatrix}\dfrac{3^p+3}{4\cdot 3^p} \\ \dfrac{3^p-1}{4\cdot 3^p} \\ \dfrac{3^p-1}{4\cdot 3^p} \\ \dfrac{3^p-1}{4\cdot 3^p}\end{bmatrix}}$$
For questions that are an odd $p$ problems away from the question you look at, the probability matrix is
$$\boxed{\begin{bmatrix}\dfrac{3^p-3}{4\cdot 3^p} \\ \dfrac{3^p+1}{4\cdot 3^p} \\ \dfrac{3^p+1}{4\cdot 3^p} \\ \dfrac{3^p+1}{4\cdot 3^p}\end{bmatrix}}$$
$p$ = 0 and $p$ = 1.¶
The probability matrices are
\begin{align*} \begin{bmatrix}A_0 \\ B_0 \\ C_0 \\ D_0\end{bmatrix} &= \begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix} \\ \\ &= \boxed{\begin{bmatrix}\dfrac{3^0+3}{4\cdot 3^0} \\ \dfrac{3^0-1}{4\cdot 3^0} \\\ \dfrac{3^0-1}{4\cdot 3^0} \\ \dfrac{3^0-1}{4\cdot 3^0}\end{bmatrix}} \\ \\ \\ \\ \begin{bmatrix}A_1 \\ B_1 \\ C_1 \\ D_1\end{bmatrix} &=\begin{bmatrix}0 & \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & 0 & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & 0 & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} & 0 \end{bmatrix} \times \begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix} \\ \\ &= \begin{bmatrix}0 \\ \dfrac{1}{3} \\ \dfrac{1}{3} \\ \dfrac{1}{3}\end{bmatrix} \\ \\ &= \boxed{\begin{bmatrix}\dfrac{3^1-3}{4\cdot 3^1} \\ \dfrac{3^1+1}{4\cdot 3^1} \\ \dfrac{3^1+1}{4\cdot 3^1} \\ \dfrac{3^1+1}{4\cdot 3^1}\end{bmatrix}} \end{align*}
$p = k$.¶
Assume true for some even $k$.
$$\begin{bmatrix}A_k \\ B_k \\ C_k \\ D_k\end{bmatrix} = \begin{bmatrix}\dfrac{3^k+3}{4\cdot 3^k} \\ \dfrac{3^k-1}{4\cdot 3^k} \\\ \dfrac{3^k-1}{4\cdot 3^k} \\ \dfrac{3^k-1}{4\cdot 3^k}\end{bmatrix}$$
$p = k+1$ and $p = k+2$.¶
\begin{align*} \begin{bmatrix}A_{k+1} \\ B_{k+1} \\ C_{k+1} \\ D_{k+1}\end{bmatrix} &= \begin{bmatrix}0 & \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & 0 & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & 0 & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} & 0 \end{bmatrix} \times \begin{bmatrix}\dfrac{3^k+3}{4\cdot 3^k} \\ \dfrac{3^k-1}{4\cdot 3^k} \\ \dfrac{3^k-1}{4\cdot 3^k} \\ \dfrac{3^k-1}{4\cdot 3^k}\end{bmatrix} \\ \\ &= \begin{bmatrix}3\cdot \dfrac{3^k-1}{4\cdot 3^{k+1}} \\ \dfrac{3^k+3}{4\cdot 3^{k+1}} + 2\cdot \dfrac{3^k-1}{4\cdot 3^{k+1}} \\ \dfrac{3^k+3}{4\cdot 3^{k+1}} + 2\cdot \dfrac{3^k-1}{4\cdot 3^{k+1}} \\ \dfrac{3^k+3}{4\cdot 3^{k+1}} + 2\cdot \dfrac{3^k-1}{4\cdot 3^{k+1}}\end{bmatrix}\\ \\ &= \boxed{\begin{bmatrix}\dfrac{3^{k+1}-3}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}}\end{bmatrix}} \\ \\ \\ \begin{bmatrix}A_{k+2} \\ B_{k+2} \\ C_{k+2} \\ D_{k+2}\end{bmatrix} &= \begin{bmatrix}0 & \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & 0 & \dfrac{1}{3} & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & 0 & \dfrac{1}{3} \\ \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} & 0 \end{bmatrix} \times \begin{bmatrix}\dfrac{3^{k+1}-3}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}} \\ \dfrac{3^{k+1}+1}{4\cdot 3^{k+1}}\end{bmatrix}\\ \\ &= \begin{bmatrix}3\cdot \dfrac{3^{k+1}+1}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+1}-3}{4\cdot 3^{k+2}} + 2\cdot \dfrac{3^{k+1}+1}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+1}-3}{4\cdot 3^{k+2}} + 2\cdot \dfrac{3^{k+1}+1}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+1}-3}{4\cdot 3^{k+2}} + 2\cdot \dfrac{3^{k+1}+1}{4\cdot 3^{k+2}}\end{bmatrix}\\ \\ &= \boxed{\begin{bmatrix}\dfrac{3^{k+2}+3}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+2}-1}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+2}-1}{4\cdot 3^{k+2}} \\ \dfrac{3^{k+2}-1}{4\cdot 3^{k+2}}\end{bmatrix}} \end{align*}
Solution¶
\begin{align*} \begin{bmatrix}A_0 \\ B_0 \\ C_0 \\ D_0\end{bmatrix} &= \begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix} \\ \\ \\ \begin{bmatrix}A_1 \\ B_1 \\ C_1 \\ D_1\end{bmatrix} &= \begin{bmatrix}0 \\ \dfrac{1}{3} \\ \dfrac{1}{3} \\ \dfrac{1}{3}\end{bmatrix} \\ \\ \\ \begin{bmatrix}A_2 \\ B_2 \\ C_2 \\ D_2\end{bmatrix} &= \begin{bmatrix}\dfrac{1}{3} \\ \dfrac{2}{9} \\ \dfrac{2}{9} \\ \dfrac{2}{9}\end{bmatrix} \\ \end{align*}
Answer¶
Charlie sees the first answer, should choose any different letter as the second answer, and choose the same answer as the one he saw for the third.
$$\boxed{1 + \dfrac{1}{3} + \dfrac{1}{3} = \dfrac{5}{3}}$$
Extra Credit¶
Oh no, Charlie’s teacher is giving another pop quiz! This time, there are seven multiple choice questions, each with four choices (A, B, C, and D). Charlie still hasn’t studied, and his teacher remains obsessive about avoiding any repeating correct answers.
Charlie has one chance to glance over at his neighbor’s test and spot a single correct answer before the neighbor notices and prevents Charlie from seeing any others.
Which of the seven answers should Charlie look at? And, if he does so, then what score should he expect to earn on this quiz, on average?
Solution¶
Based on the matrices found in the induction above, Charlie should chose the same answer as that of which he looked at for questions an even number away in order to obtain the maximum probability,
$$\dfrac{3^p+3}{4\cdot 3^p}$$
Charlie should chose the any answer but the one he looked at for questions an odd number away in order to obtain the maximum probability,
$$\dfrac{3^p+1}{4\cdot 3^p}$$
Note that
$$\dfrac{3^p+1}{4\cdot 3^p} \times \dfrac{3}{3} = \dfrac{3^{p+1}+3}{4\cdot 3^{p+1}}$$
Consecutive questions have the same likelihood of being correct.
Assuming Charlie is looking at the first question, the probability of getting each question correct is
$$\bigg[1, \dfrac{1}{3}, \dfrac{1}{3}, \dfrac{7}{27}, \dfrac{7}{27}, \dfrac{61}{243}, \dfrac{61}{243} \bigg]$$
The fractions from the induction are both decreasing functions, so it is in Charlie's best interest to choose the middle question to have the maximum likelihood throughout the test.
If Charlie is looking at the fourth question, the probability of getting each question correct is
$$\bigg[\dfrac{7}{27}, \dfrac{1}{3}, \dfrac{1}{3}, 1, \dfrac{1}{3}, \dfrac{1}{3}, \dfrac{7}{27} \bigg]$$
Looking at the third or fifth question first yields the same fractions but a $\dfrac{7}{27}$ is moved from one end to the other.
Answer¶
\begin{align*}
P &= \dfrac{7}{27} + \dfrac{1}{3} + \dfrac{1}{3} + 1 + \dfrac{1}{3} + \dfrac{1}{3} + \dfrac{7}{27} \\
&= 2\times \dfrac{14}{27} + 4\times \dfrac{4}{3} + 1 \\
&= \dfrac{14}{27} + \dfrac{36}{27} + \dfrac{27}{27} = \boxed{\dfrac{77}{27} \approx 2.852} \\
\end{align*}
