# Multiple choice exam where no three consecutive answers are the same

A multiple choice test consists of 60 questions, with 4 possible answers for each question. How many multiple choice exams can we create where no three consecutive answers are the same?

I tried

• reducing the problem into two consecutive like problem (for 1, 2,3 to be same, 1-2 and 2-3 must be the same simultaneously);

• checking triples (1, 2, 3), (2, 3, 4), and so on (there are 58 of them).

Unfortunately, I did not arrive at the answer given in the book, which is $3 \times2^{60}.$

• Are you sure of that answer? There's a simple recursion...$T_n=3\times (T_{n-1}+T_{n-2})$ but I doubt that result matches.
– lulu
Apr 5 '17 at 12:17
• did you try finding the number of exams where three consecutive answers are the same ? Then you could just subtract those from total number of exams and get an answer. I feel like inclusion exclusion could help in first part. Apr 5 '17 at 12:24
• There are only two possible types of good strings...according to whether they end in one of a kind or two of a kind. Thus every good string ends in $\dots YX$ or $\dots YXX$. There are $3T_{n-1}$ of the first sort and $3T_{n-2}$ of the second sort.
– lulu
Apr 5 '17 at 12:26
• Note: as a quick way to see that the proposed answer is wrong, look at tests in which every third answer is $D$ (with no other $D's$). Clearly such a test can't have three consecutive matches in a row and there are $3^{40}$ such tests. We then remark that $3^{40}>3\times 2^{60}$ so we've already produced more good tests than the proposed solution would allow.
– lulu
Apr 5 '17 at 12:57

Let $T_n$ be the number of "good" tests of length $n$. We note that $T_1=4,T_2=16$. There is a simple recursion for $n≥3$, namely $$T_n=3T_{n-1}+3T_{n-2}$$ To see this, simply remark that every good test either ends with $\dots YX$ or $\dots YXX$ for answers $Y\neq X$. There are $3T_{n-1}$ of the first sort and $3T_{n-2}$ of the second.
That recursion has a closed form, though it isn't especially pleasant. The characteristic equation is $$\lambda^2=3\lambda+3\implies \lambda = \frac 12\left(3\pm\sqrt {21}\right)$$ Some unpleasant but straightforward algebra then gives $$T_n=\frac 2{21}\left(7+\sqrt {21}\right)\lambda_+^n+\frac 2{21}\left(7-\sqrt {21}\right)\lambda_-^n$$
Where $\lambda_\pm$ denotes the root with the appropriate sign. Note that $$T_{60}\approx 1.1\times (3.79)^{60}$$ is a lot higher than the number your answer proposes.
Note: to simplify the calculation it's easier to extend your series down to $T_0=\frac 43$. That value doesn't make physical sense in your test designing context, but it does mean that $T_2=3\times\left(T_1+T_0\right)$ so it makes sense in the recursion.