Probability Time

Count the number of ways a coin can be tossed 10 times and never have heads come up on consecutive tosses. Imagine putting 10 coins reflecting the tosses in order in a row. When $k$ heads are tossed, $10-k$ tails are tossed. There are $10-k+1$ positions for each of the heads, so there are ${10-k+1 \choose k}$ total arrangements. Therefore, the total number of ways to toss the coin with this restriction is $\sum_{k=0}^{10}{10-k+1 \choose k}=144$ .

Clearly, there are $2^{10}$ possible outcomes when flipping a coin ten times. Therefore, the probability that heads never occurred on consecutive tosses is $\frac{144}{2^{10}}=\frac{9}{64}$ , so the answer is $\boxed{73}$ .

Let $N^H(n)$ and $N^T(n)$ denote the number of coin-toss sequences of length $n$ and ending with Heads and Tails respectively, such that no two heads occur on consecutive tosses. Then it easily follows that the following recursion holds $N^H(n+1)=N^T(n)$ $N^T(n+1)=N^H(n)+N^T(n)$ We also have the initial condition that $N^H(2)=1, N^T(2)=2$ Thus we can solve for $N^H(10)=55, N^T(10)=89$ (by hand, by matrix exponents or by a computer program) and find that the number of permissible sequence of length $10$ is simply $N^H(10)+N^T(10)=144$ . Hence the required probability is $\frac{55}{2^{10}}=\frac{9}{64}$ .