The problem statement is as follows: A fair coin is to be tossed $10_{}^{}$ times. Let $i/j^{}_{}$, in lowest terms, be the probability that heads never occur on consecutive tosses. Find $i+j_{}^{}$.

My solution was to consider the sequence of flips as a string of either [Head then Tail] or [Tail]. Let $x$ represent the number of [Head then Tail] and $y$ represent the number of [Tail]. Then $2x$ + $y$ = $10$.

Then I did casework for each value of $x$:

When $x = 0$ it is bijective to the number of arrangements of $AAAAAAAAAA$, which is $1$.

Then, when $x = 1$ it is bijective to the number of arrangements of $AAAAAAAAB$, which is 9 and so on...

The sum of these values turns out to be $89$ and the number of ways to flip is $1024$, but that is wrong. What is wrong with my solution? Thanks!

  • $\begingroup$ What about [Tail then Head]? $\endgroup$ – Alex Nolte May 27 '18 at 0:43
  • $\begingroup$ your $x=1$ should have $10$ arrangements not $9$. What were your other values? $\endgroup$ – Henry May 27 '18 at 0:44
  • $\begingroup$ from your description you won't count the case all tails except the final is head. $\endgroup$ – Postal Model May 27 '18 at 0:45

Your starting point has two flaws:

  • It forgets about Heads that could occur at the end of the string
  • It makes no difference between [Tails] and [Tails preceded by Heads] (in other words the equation $2x+y=10$ is wrong).

One way to get there without much trouble is this one:

  1. Fix the amount of Heads (could be anything between $0$ and $5$),
  2. Place them in a row, with one mandatory Tails in between each pair,
  3. Use the Stars and Bars formula to compute the number of ways to add the remaining Tails.

Your $89$ is presumably $1+9+28+35+15+1$

It should be $1+10+36+56+35+6$

Since your $89$ would be correct for the numerator with nine coin tosses, you have presumably missed all those starting with heads, or all those finishing with heads

It is not a coincidence that $89$ and $144$ are consecutive Fibonacci numbers, and an alternative approach would use a simple recurrence


I know there has been an answer for a while but I think I've got an easier approach and maybe it's worth writing.

So I will show the solution inductive: let's assume after $i$ flips we had $n_{i,h}$ ways to end with a head and $n_{i,t}$ ways to end with a tail.

So let's observe the (n+1)th flip:

If the nth was a head we will count the (n+1)th only if it's a tail.

If the nth was a tail we will count the (n+1)th anyway.

so that means $n_{i+1,t} = \left(n_{i,t} + n_{i, h} \right)$ and $n_{i+1,h} = n_{i, t}$.

And we have the base case where $n_{1,h} = n_{1, t} = 1$ So you have now a nice recursive formula you can use, but let's try to make it simpler.

There is many ways to approach this, one of them is with matrices, let's observe the following matrix:

$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} $

and the product:

$ A . \begin{pmatrix} x_{1} \\ x_{2} \\ \end{pmatrix} = \begin{pmatrix} x_{1} + x_{2}\\ x_{1} \\ \end{pmatrix} $

so if $ \begin{pmatrix} x_{1} \\ x_{2} \\ \end{pmatrix} $ represents the ith try, $\left (A. \begin{pmatrix} x_{1} \\ x_{2} \\ \end{pmatrix} \right ) $ will represent the (i+1)th try with $x_1$ the number of tails and $x_2$ the number of heads.

This is especially useful, when we have n tries: $A * (A* (\dots * (A* \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} ))) = A^n * \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} $ so all you really need to do is to calculate $A^{n-1}$ and multiply it with $ \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} $ Then the answer will be the sum of $x_1$ and $x_2$ in the resulting vector.

One more approach for it, is after observing the fact that the number of tails is the sum of the last number of tails and last number of heads and the number of heads is the last number of tails we can observe how they evolve:

tails: 1, 2, 3, 5, 8, ...

heads: 1, 1, 2, 3, 5, ...

It is clear that the each number is the sum of the last two numbers before it, which is exactly the Fibonacci numbers in definition. So what we are exactly looking for is fib(n+1) + fib(n) = fib(n+2), for fib(n+1) the number of ways to end with tail and fib(n) is the number ways to end with head.

In your case the answer is fib(12) = 144.

P.S. Matrix exponentiation is one of the most famous ways to calculate Fibonacci numbers.


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.