Ilya Muromets meets the three-headed Zmei Gorynych. And the battle begins. Every minute Ilya cuts off one of Zmei's heads. With a probability of $1 / 4$, two new heads grow in place of the severed one, with a probability of $1 / 3$ - only one new head, and with a probability of $5 / 12$ - no heads at all. The Zmei is considered defeated if he has no heads left. Find the probability that Ilya will eventually defeat the Zmei.
Strikes by Ilya Muromets, in which the number of heads changes, are called successful.

Let's find the probability that at some point there will be a last successful strike. This means that starting from this point, there will be no more successful strikes, that is, all strikes will be unsuccessful. The probability of this is $1 / 3 \cdot 1 / 3 \cdot 1 / 3 \cdot \ldots$ $=0$.

Thus, there will be no last successful strike, but there will be an infinite subsequence of successful strikes, which we will consider, ignoring all other strikes.

The probability of a successful strike is $2 / 3$. The conditional probability that the number of heads increases when a strike is successful is $1 / 4 : 2 / 3 = 3 / 8$.

Similarly, the conditional probability that the number of heads decreases when a strike is successful is $5 / 12 : 2 / 3 = 5 / 8$.

This leads to a standard one-dimensional random walk problem. Suppose that as a result of a certain series of successful strikes, the number of heads of the Serpent has decreased by one compared to what it was. Let's call this event $D$, and its probability $x$.

There are two possibilities.

1) As a result of the first successful strike, the number of heads decreased by one (event $M$, probability $5 / 8$). In this case, event $D$ has already occurred - its conditional probability is 1.
2) As a result of the first successful strike, the number of heads increases by one (event $N$, probability $3 / 8$). In this case, event $D$ will occur only if the number of heads decreases by 2 - by one, and then by another one. Therefore, the conditional probability of event $D$ in this case is $x^2$.

By the formula for total probability, $x = P(D) = P(D \mid M) \cdot P(M) + P(D \mid N) \cdot P(N) = 5 / 8 + 3 / 8 x^2$.

From this, $x = 1$ or $x = 5 / 3$. The second root is extraneous. Therefore, event $D$ is certain.

Thus, sooner or later, the number of heads will inevitably decrease from three to two. Then, for the same reason, the number of heads will decrease to one and, finally, to zero. The Serpent has no chance.

## Answer