Combinatorics Olympiad Problem 5

Probability Level 4

Another coin toss problem!

A fair coin is tossed $10$ times. What is the probability that two heads do not occur consecutively? Express the probability as a decimal.

This problem is not original. This is a hard problem, roughly at the difficulty level of a problem in the BMO. This problem is part of this set .

The answer is 0.140625.

4 solutions

Brian Charlesworth
Mar 7, 2015

Let $h(n)$ be the number of sequences of heads and tails of length $n$ for which two heads do not appear consecutively.

Then $h(1) = 2$ , ( $H, T$ ), and $h(2) = 3,$ ( $HT, TH, TT$ ).

For $n \gt 2$ we can have either

(i) a sequence beginning with a tail followed by $n - 1$ tosses with no two consecutive heads, or

(ii) a sequence beginning with a head, then a tail, followed by $n - 2$ tosses with no two consecutive heads.

Thus for $n \gt 2$ we have $h(n) = h(n - 1) + h(n - 2).$ So with our initial values of $h(1) = 2$ and $h(2) = 3$ we end up with a shifted Fibonacci sequence, with successive terms $2, 3, 5, 8, 13, 21, 34, 55, 89$ and $h(10) = 144.$

Now as there a total of $2^{10} = 1024$ possible sequences of $10$ tosses without restrictions, the desired probability is $\frac{144}{1024} = \frac{9}{64} = \boxed{0.1406}$ to 4 decimal places.

Great solution!

A Former Brilliant Member - 6 years, 3 months ago

Thanks. Nice problem. :)

Brian Charlesworth - 6 years, 3 months ago

Not mine, unfortunately:(

A Former Brilliant Member - 6 years, 3 months ago

Well explained. I got it the same way, but I can't put it in words to write a solution. Getting really rusty here. Great problem though. Keep up the good work! :)

Francis Gerard Magtibay - 6 years, 3 months ago

I got this problem wrong because for some reason I was trying to solve for 9 flips, but here are my two cents:

Python:

from itertools import product
from fractions import Fraction as frac
top = 0
bottom = 0
for combo in product('ht',repeat=10):
    if 'hh' not in ''.join(combo):
        top += 1
    bottom += 1
print "Answer:", frac(top,bottom)

Brock Brown - 6 years, 3 months ago

Deb Biswas
Mar 8, 2015

let, we get no head. It is done in 1 way. when we get 1 head, no. of cases are 10. when we get 2 heads, no. of cases are 9C2.
when we get 3 heads, no. of cases are 8C3.
....it is continued upto 5 heads, as no more case will satisfy the condition. so total no. of cases are- 1+10+9C2+8C3+7C4+6C5=144 therefore the required probability is-(144/2^10)=0.141

The process is great but i did same as the first solution

Aritra Chakraborty - 6 years, 3 months ago

Rahul Saxena
May 19, 2015

someone tell me what is BMO??

Grijesh Agrawal
Apr 1, 2015

This question can be broken down to -- 'how many ways can there be that x number of heads are there (in 10 flips) without any heads being consecutive'. Only Possibilities: (x >= 0 and x <= 5) Because if x > 5 then at least 2 heads will have to be consecutive. Now, assume,

x = number of heads 10 - x = number of tails

Case 1: x = 0 => number of ways = 1

Case 2: x = 1 => number of ways = 10C1 (Think of it as choosing 1 gap from 10 gaps when 9 tails are placed in a line.) (- Gaps are places between 2 tails.)

Case 3: x = 2 => number of ways = 9C2

Case 4: x = 3 => number of ways = 8C3

Case 5: x = 4 => number of ways = 7C4

Case 6: x = 5 => number of ways = 6C5

So, probability of 2 heads not being consecutive = 144 / 2^10 = 0.1406

Combinatorics Olympiad Problem 5

The answer is 0.140625.

4 solutions

0 pending reports