Not Too Many Heads
If a coin is flipped 10 times, find the number of possible sequences of heads and tails such that there is at most one pair of consecutive heads.
For example, T T T T T H T H T H T H T H T H H T T T T T T T T T T T T T all work, but T H H T T T H T H H does not.
The answer is 379.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
We can solve pattern avoidance problems using directed graphs.
The di-graph of this problem can be written as:
⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ I H T H H T ′ H ′ I 0 0 0 0 0 0 H 1 0 1 0 0 0 T 1 1 1 0 0 0 H H 0 1 0 0 0 0 T ′ 0 0 0 1 1 1 H ′ 0 0 0 0 1 0 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
'I' is the initial state.
'H' and 'T' are the states which indicate that the sequence seen does not contain HH.
H' and T' are the states which tells that the sequence seen contains exactly one pair of HH.
Let's call the matrix A, the answer we seek is the sum of first row in A^10, which is 379.
A 1 0 = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0 0 0 0 0 0 5 5 3 4 5 5 0 0 0 8 9 5 5 8 9 0 0 0 3 4 2 1 3 4 0 0 0 1 3 0 1 0 5 1 3 0 5 5 8 9 5 5 7 1 5 9 7 1 3 4 5 5 3 4 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
But we can do more with the matrix.
Find the characteristic polynomial of the matrix, which is x 6 − 2 x 5 − x 4 + 2 x 3 + x 2
It is the characteristic equation of the required recurrence: x 4 − 2 x 3 − x 2 + 2 x + 1 = 0
And, we can write the recurrence equation from the above equation:
f n = 2 f n − 1 + f n − 2 − 2 f n − 3 − f n − 4 f 0 = 1 , f 1 = 2 , f 2 = 4 , f 3 = 7
From the characteristic equation, we also get the formula:
f n = 2 n ( 5 − 1 ) n ( 5 n − 5 0 1 3 5 − 2 5 ) ( − 1 ) n + 2 n ( 5 + 1 ) n ( 5 n + 5 0 1 3 5 + 2 5 )
I don't think that's the fastest method to solve the problem; I think just counting the cases is faster (my method)
Log in to reply
This solution is much faster than the length of the solution suggests. I think it might be slower for those without as much experience with recursion, but I think it is faster otherwise. Also, it is less prone to errors, a problem with casework.
Believe me, I LOVE solving problems with recursions; however, I personally believe that this problem is quicker to solve with a stars-and-bars type approach.
Log in to reply
Could you explain a little bit of your casework? Maybe it is faster for you, but I cannot see it being faster for me.
I solved it with stars-and-bars as well. There are obvious patterns to the cases, which speeds up the solving process anyways.
Though I've never tried solving combinatorics problems by recursion, so I will keep that in mind.
Case 1: 4 tails Subcase 1: No consecutive heads Subcase 2: One consecutive pair of heads After proceeding like this (stars-and-bars, where you insert the heads into the spaces), you can easily find a general formula for the valid cases for each amount of tails, which will eventually sum up to 379, as desired.
Log in to reply
Uhhh 14 cases seems like it would take a nontrivial amount of time and possible errors. If you see the recursion quickly, that is probably faster.
Why do we have to consider all 4 cases? Couldn't we just consider the cases of having just 1 pair of heads or having no pairs of heads?
Log in to reply
You also have to consider the last flip. Consider if there is 1 pair of heads. If the last flip was tails, we can have the next flip be either. If the last flip was heads, the next flip can only be tails. Because there is a difference, we have to keep the two separate.
Sorry, 8 cases. Mistyped.
Log in to reply
Well the 8 cases are there just to see what happens when adding each of the 2 possible flips to each of the 4 possible states.
I spent ages trying to understand how this question worked, and eventually stumbled upon a solution that my limited GCSE maths could provide.
Let us first consider the case of no consecutive heads. We can see that with one flip, there can only be two outcomes, with two flips, there can be 3, and with three there can be 5. Immediately, we can see that this follows the fibonacci sequence.
Then we can split it up into cases.
With no consecutive heads, there will be 144 options (continuing the fibonacci sequence).
If we start with a consecutive heads, then the next coin must be a tails, and the final 7 will follow the fibonacci sequence. So there will be 34 options for this, multiplied by two, as this is symmetrical to ending with a pair of consecutive heads.
We can then continue this logic for all the other cases (there are only 5), and the sum of all of them is equal to 3 7 9
An is required and T.....,HT......,HHT....(fib(n-3)) (no of sequences having no consecutive H) An=A(n-1)+A(n-2)+fib(n-3) Initial conditions A1=2 A2=4 A3=7
Let t(n) equal number of sequences that doesn't contain 2 consecutive heads with length n and end with a Tail. Similarly, h(n) equal number of sequences that doesn't contain 2 consecutive heads with length n and end with a Head.
it is obvious that
h(n) = t(n-1) , because the last coin can be a head if and only if the one before it was a tail.
and t(n) = t(n-1) + h(n-1) , because the last coin can be a tail whatever the one before it was.
combining the 2 equations t(n) = t(n-1) + t(n-2)
let nth term of Fibonacci sequence be fib(n): Read more about Fibonacci Sequence here: http://en.wikipedia.org/wiki/Fibonacci_number
Since t(1) = 1 and t(2) = 2 , t(n) = fib(n+1) ,
Total number of solutions at n = t(n) + h(n) = t(n) + t(n-1) = fib(n+1) + fib(n) = fib(n+2)
Solution for all sequences of length 10 contain NO consecutive heads = fib(12) = 144
consider inserting two consecutive H (Putting HH) in indeces i and i+1 (1<i<9)
so we will need to insert a T before it and a T after it so we will insert (THHT) if there were x coins before THHT then there will be 10 - 4 - x = 6-x coins after
number of possible sequences of coins before THHT = fib(x+2)
number of possible sequences of coins after THHT = fib(6-x+2) = fib(8-x)
Number of possible sequences = fib(x+2)*fib(8-x) (since these terms are independent)
since 0<=x<=6 we need to take sigma fib(x+2)*fib(8-x) = 167
putting the HH at the beginning will enforce us to put a T after it then we have fib(7+2) possible sequences = 34 Similarly putting the HH at the end will yield other 34 sequences
Total Number of solutions = 144 + 167 + 34*2
I solved this as a Markov Chain problem. I first set up 5 states: State 0: I currently have 0 consecutive heads and the last coin flipped was not a head. State 1: I currently have 0 consecutive heads and the last coin flipped was a head. State 2: I currently have 1 consecutive heads and the last coin flipped was a head. State 3: I currently have 2 consecutive heads and the last coin flipped was not a head. State 4: Game Over (i.e. I currently have 2 or more consecutive heads)
Then I make my probability matrix P where the i,j entry is the probability of going from state i to state j after a coin flip. This matrix ends up having a lot of 0's and (1/2)'s. Taking the 10th power of this matrix, the 0,4 entry of P tells us the probability of going from state 0 (which is our starting state) to state 4 (the "losing"state), denote this by p. Thus the answer is the total number of sequences minus the number of "losing" sequences or simply 2^10 -(2^10*p).
I had tried a method that was pretty much exactly yours but I had gotten a wrong answer because I had accidentally written my 8 like a 6, didn't notice it until now. Sometimes it's nice to try different approaches though :)
We use recursion . There are four possible states for a sequence of heads and tails:
No pair of consecutive heads and ends in a heads (we'll denote this as state H 0 and sequence H 0 n ).
No pair of consecutive heads and ends in a tails (we'll denote this as state T 0 and sequence T 0 n ).
One pair of consecutive heads and ends in a heads (we'll denote this as state H 1 and sequence H 1 n ).
One pair of consecutive heads and ends in a tails (we'll denote this as state T 1 and sequence T 1 n ).
Then, we can see that the base cases are H 0 1 = 1 , T 0 1 = 1 , H 1 1 = 0 , T 1 1 = 0 . For the recurrence, we consider the eight cases:
If a sequence H 0 is followed by a heads, we get H 1 , and otherwise we get T 0 .
If a sequence T 0 is followed by a heads, we get H 0 , and otherwise we get T 0 .
If a sequence H 1 is followed by a heads, we get a sequence that is not allowed, and otherwise we get T 1 .
If a sequence T 1 is followed by a heads, we get H 1 , and otherwise we get T 1 .
The recursion is then H 0 n + 1 T 0 n + 1 H 1 n + 1 T 1 n + 1 = T 0 n = H 0 n + T 0 n = H 0 n + T 1 n = H 1 n + T 1 n Applying the recurrences, we find that H 0 1 0 = 5 5 , T 0 1 0 = 8 9 (the Fibonacci numbers are not a coincidence), H 1 1 0 = 1 0 5 , and T 1 1 0 = 1 3 0 , and the answer is 5 5 + 8 9 + 1 0 5 + 1 3 0 = 3 7 9 .