Combinatorics Olympiad Problem 4

Probability Level 5

If you toss a fair coin 20 times, what is the probability of 5 successive heads at any time? Express the answer as a decimal and round it off to 7 decimal places.

This problem is not original. It is roughly as difficult as a problem in the BMO. This problem is part of this set .

The answer is 0.2498703.

3 solutions

Eilon Lavi
Mar 12, 2015

Let $W(n)$ be the number of permutations of length n of coin flips containing 5 successive heads. Our answer is $\dfrac{W(20)}{2^{20}}$

Let us look for a recursive formula for $W(n)$ .

Consider coin permutations of length n, for a large n. We can separate these permutations into two types:

Type A: Permutations that have 5 successive heads in the first n-1 coins.

For each permutation in $W(n-1)$ , we can stick an extra H or T at the end to get a unique permutation of this type. So there are $2 W(n-1)$ permutations of this type.

Type B: Permutations that do not have 5 successive heads in the first n-1 coins

In that case, the 5 successive heads must occur at the very end.

...<---length n-5-->...HHHHH

But the coin in the $n-5^{th}$ spot cannot be heads, since that would make 5 successive heads in the first n-1 coins.

...<---length n-6-->...THHHH

What permutations can we put in in our n-6 long hole? Any n-6 long permutation that does not contain 5 successive heads.

Therefore there are $2^{n-6}-W(n-6)$ permutations of this type.

We thus obtain the recursive formula $W(n)=2W(n-1)+2^{n-6}-W(n-6)$

The formula is valid for $n \ge 6$ and we have the initial values $W(k)=0 , k \le 4$ and $W(5)=1$ .

20 is small enough, so it is not too terrible to calculate $W(20)$ bottom up.

It turns out $W(20)=262008$

$\dfrac{262008}{2^{20}} = 0.2498703$

C code:

int main(){
    int ways[21];
    for (int i=0;i<=4;i++) ways[i]=0;
    ways[5]=1;
    for (int n=6;n<=20;n++) ways[n]=2*ways[n-1]+twopow(n-6)-ways[n-6];
    printf("%d", ways[20]); 
}
int twopow(int n){
    return (n==0?1:2*twopow(n-1));
}

Eilon Lavi - 6 years, 3 months ago

great...! ...

Zeeshan Ali - 6 years, 2 months ago

Calvin Lin Staff
Mar 10, 2015

[This is not a solution. It is converted from a note by Satyendra asking why he had a mistake in his understanding. I think it is valuable for others to understand this mistake, so I reproduced it here.]

Here is my approach:
Five consecutive coins can be chosen in 15 ways.Let us say we choose the first 5 coins.The probability that all of them show heads is $\dfrac{1}{2^5}$ .Because we want exactly 5 consecutive heads the other 15 coins should show tails,the probability of that is $\dfrac{1}{2^{15}}$ .Thus,probability of 5 consecutive heads is $\dfrac{1}{2^{20}}*15$ . WHAT IS WRONG?

Other 15 coins need not show tails... So probability should be much more than what you have calculated... Eilon has got the accurate answer ... I checked on Wolfram..

Anuj Mishra - 5 years, 11 months ago

Zeeshan Ali
Apr 14, 2015

20 coins are tossed where 5 are expected to be heads therefore the probability is; 5/20 == 1/4 == 0.25.

That awkward moment when rounding off of Brilliant answers gets yours right

Vishnu Bhagyanath - 5 years, 2 months ago

Combinatorics Olympiad Problem 4

The answer is 0.2498703.

3 solutions

0 pending reports