No Double Heads

Let $X_n$ be the number of ways of thowing $n$ coins without obtaining two successive heads. To count $X_n$ , we note that if the first toss is $H$ , the second toss must be $T$ , while no restriction is placed on the second toss if the first toss is $T$ . Thus the number of ways of tossing $n$ coins without obtaining two successive heads, if the first toss is $H$ , is $X_{n-2}$ , while the number of ways of tossing $n$ coins without obtaining two successive heads, if the first toss is $T$ , is $X_{n-1}$ . Thus $X_n \; = \; X_{n-1} + X_{n-2}$ Since it is easy to see that $X_1 = 2$ and $X_2 = 3$ , we deduce that $X_n = F_{n+2}$ can be expressed in terms of the Fibonacci numbers. Thus the probability that the customer wins, if $n$ coins are tossed, is $p_n \; = \; \frac{F_{n+2}}{2^n}$ Note that $2^{n+1}(p_n - p_{n+1}) \; = \; 2F_{n+2} - F_{n+3} \;= \; F_{n+2} - F_{n+1} \;\ge \; 0$ so that $p_n$ is a decreasing sequence. We calculate $p_1 = 1$ , $p_2 = \tfrac34$ , $p_3 = \tfrac58$ , $p_4 = \tfrac12$ and $p_5 = \tfrac{13}{32} < \tfrac12$ . Thus the casino owner sets $n = \boxed{5}$ .

If the casino sets n = 4, then the punter's winning combinations (out of 16 possibilities) are TTTT, TTTH, TTHT, THTT, HTTT, HTHT,THTH and HTTH.

Any other combinations have consecutive Hs and hence lose.

With n = 4 the casino has an 8 out of 16 chance of winning so this is not acceptable.

Increasing n to 5 will decrease the punter's chance of a win; because there are 1 + 5 + 5 + 1 = 12 acceptable placements of 5, 4, 3 and 2 Ts in a set of five flips.

The punter has a 12 out of 32 chance of a win, so n = 5 fulfills the casino's requirement with a 20 out of 32 chance.

Make n bigger and the punter's chance of winning gets progressively worse.

In the general case, when the coin is fair and p=1/2, the formula for average number of tosses to get n consecutive heads=2^(n+1)-2.

So, set one less than this to favour the casino in case of two consecutive heads (n=2):

Answer=(2^3-2)-1=5

After each coin toss, define the current state as either Safe (S), Dangerous (D) or Lost (L) where S means the last toss was tails, D means the last toss was heads (and in both cases the sequence does not yet contain two consecutive heads) and L means that two consecutive heads have already been thrown. For the next toss, S could lead to S or D; D could lead to S or L; L will lead to L.

Hence we can calculate the new range of possibilities by the formula S(new) = S+D; D(new) = S; L(new) = 2L+D

Beginning with [S,D,L] = [1,1,0] after the first toss we generate the following:

2nd toss: [2,1,1]

3rd toss: [3,2,3]

4th toss: [5,3,8]

5th toss: [8,5,19]

It is with five tosses of the coin that the number of losses becomes greater than half the total number of possibilities.

I just worked it out for 4, saw it was 50% and thus answered 5.

The chances of getting two heads in a row are (1/2)^2 per 2 throws. So theoretically every 8 throws you get head twice in a row at least once. Divide it by 2 and you get for every 4 throws a 50% chance of getting two heads in a row. the first number n that will give the casino the lowest chances that remain above 50% is 4+1 which is equal to 5