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}.$

  • $\begingroup$ 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. $\endgroup$
    – lulu
    Apr 5 '17 at 12:17
  • $\begingroup$ im also skeptical about this answer. By the way how did you get recursion? @lulu $\endgroup$
    – Salih
    Apr 5 '17 at 12:19
  • $\begingroup$ 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. $\endgroup$
    – asddf
    Apr 5 '17 at 12:24
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Apr 5 '17 at 12:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.