We flip a fair coin 12 times in a row and record the results of the flips. What is the probability that no three heads follow each other?
I. Solution. The probability to be calculated is the ratio of the number of favorable elementary events to the total number of elementary events.

The total number of elementary events is the number of 12-long head-tail sequences. There are $2^{12}=4096$ such sequences, since at each of the 12 tosses, we can get either a head or a tail with equal probability.

The number of favorable elementary events is the number of head-tail sequences in which three heads do not follow each other. Let's count these cases.

Let's count according to how many tails are in them. Let $i$ be the number of tails, $i$ takes values from 0 to 12.

The $i$ tails divide the sequence into $i+1$ "parts". In these $i+1$ parts, $12-i$ heads are distributed such that in each part there can be 0, 1, or 2 of them.

If $i=12$, then three heads definitely do not follow each other. Therefore, 12 tails have 1 possible arrangement.

If $i=11$, then the 1 head can stand in any of the 12 parts, which is $\binom{12}{1}=12$ possibilities.

If $i=10$, then the 2 heads can be placed in a pair in 11 parts, which is $\binom{11}{1}=11$ possibilities; or separately, which is $\binom{11}{2}=55$ possibilities. Together, this is

$$
11+55=66
$$

possibilities.

If $i=9$, then in the 10 parts created, the 3 heads can stand in a pair and one separately, which is $\binom{10}{1} \cdot\binom{9}{1}=90$ possibilities; or separately, which is $\binom{10}{3}=120$ possibilities. Together, this is

$$
120+90=210
$$

possibilities.

If $i=8$, then 9 parts are created. The 4 heads can stand in two pairs, which is $\binom{9}{2}=36$ sequences; in one pair and two separately, which is $\binom{9}{2} \cdot\binom{7}{1}=252$ sequences; or separately, which is $\binom{9}{4}=126$ possibilities. Together, this is

$$
126+252+36=414
$$

sequences.

Similarly, for any $i$, it is useful to count the number of possibilities according to how many parts there are where the heads stand in pairs. Since $12-i$ heads fall into $i+1$ parts, the number of pairs of heads is at most $\left[\frac{12-i}{2}\right]$. If the number of pairs of heads is $0 \leq k \leq\left[\frac{12-i}{2}\right]$, then the number of possibilities is $\binom{i+1}{k}\binom{i+1-k}{12-i-2 k}$, because from the $i+1$ parts, we can choose $\binom{i+1}{k}$ ways to select which parts the heads stand in pairs, and from the remaining $i+1-k$ places, there are $\binom{i+1-k}{12-i-2 k}$ possibilities to choose where to place the remaining $12-i-2 k$ heads.

Based on this, the number of possibilities for $i=7$ (where $0 \leq k \leq 2$) is:

$$
\binom{8}{0}\binom{8}{5}+\binom{8}{1}\binom{7}{3}+\binom{8}{2}\binom{6}{1}=56+280+168=504
$$

If $i=6$, then $0 \leq k \leq 3$ and the number of possibilities is

$$
\binom{7}{0}\binom{7}{6}+\binom{7}{1}\binom{6}{4}+\binom{7}{2}\binom{5}{2}+\binom{7}{3}\binom{4}{0}=7+105+210+35=357
$$

If $i=5$, then $0 \leq k \leq 3$, and for this

$$
\binom{6}{0}\binom{6}{7}+\binom{6}{1}\binom{5}{5}+\binom{6}{2}\binom{4}{3}+\binom{6}{3}\binom{3}{1}=0+6+60+60=126
$$

possibilities exist.

For $i=4$, the number of possibilities (where $0 \leq k \leq 4$) is:

$$
\begin{gathered}
\binom{5}{0}\binom{5}{8}+\binom{5}{1} \\
\binom{4}{6}+\binom{5}{2}\binom{3}{4}+\binom{5}{3}\binom{2}{2}+\binom{5}{4}\binom{1}{0}= \\
=0+0+0+10+5=15
\end{gathered}
$$

If $i \leq 4$, then every term in the sum is 0. (This also follows from the fact that at most 4 parts are created, but at least 9 heads are tossed, and for the placement of these heads in pairs, at least 5 parts would be needed.) Therefore, for fewer than 4 tails, no suitable sequence can be formed.

In total,

$$
1+12+66+210+414+504+357+126+15=1705
$$

suitable sequences exist, so the desired probability is $\frac{1705}{4096} \approx 0.416$.

II. Solution. Let's try to determine how many sequences of length $n$ do not contain three consecutive heads. Let's call such sequences "good sequences" and denote their number by $D_{n}$.

Consider the last element of a good sequence of length $n$.

If this is a tail, then the sequence is good exactly when the first $(n-1)$ elements form a good sequence. The number of such sequences is therefore $D_{n-1}$.

If the last element is a head and the second-to-last is a tail, then the sequence is good exactly when the first $(n-2)$ elements form a good sequence. The number of such sequences is therefore $D_{n-2}$.

If the last and the second-to-last elements are heads, then the sequence is good only if the $(n-2)$-th element is not a head and the sequence formed by the first $(n-3)$ elements does not contain three consecutive heads, i.e., it is a good sequence. The number of such sequences is therefore $D_{n-3}$.

A sequence of length $n$ falls into exactly one of the above cases, so it holds that $D_{n}=D_{n-3}+D_{n-2}+D_{n-1}$.

Since the tosses are independent, and at each toss, the probability of getting a tail or a head is $1/2$, the probability that a sequence of $n$ tosses is good is $\frac{D_{n}}{2^{n}}$.

In the problem, $n=12$, so we need to determine $D_{12}$ using the recursive formula. For 1 or 2 tosses, three consecutive heads definitely do not appear, so $D_{1}=2^{1}=2$ and $D_{2}=2^{2}=4$. For 3 tosses, the HHH sequence is not good, so $D_{3}=2^{3}-1=7$. From here, $D_{4}=D_{1}+D_{2}+D_{3}=2+4+7=13 ; D_{5}=D_{2}+D_{3}+D_{4}=4+7+13=24 ; D_{6}=44 ;$ $D_{7}=81 ; D_{8}=149 ; D_{9}=274 ; D_{10}=504 ; D_{11}=927 ; D_{12}=274+504+927=1705$.

The desired probability is $\frac{1705}{2^{12}}=\frac{1705}{4096} \approx 0.42$.