Ivan the Tsarevich fought with the three-headed and three-tailed Zmey Gorynych. With one blow, he could cut off either one head, one tail, two heads, or two tails. But if he cut off one tail, two would grow back; if he cut off two tails, a head would grow back; if he cut off a head, a new head would grow back, and if he cut off two heads, nothing would grow back. How should Ivan the Tsarevich act to cut off all the heads and all the tails of the Zmey as quickly as possible
We need to ensure that Zmey Gorynych has an even number of heads and no tails. To achieve this, we first need to reach a certain number of tails.

## Solution

Notice that cutting off one head is meaningless. There are three types of strikes left: with the first, the number of tails increases by 1; with the second, the number of tails decreases by 2, but the number of heads increases by 1; with the third, the number of heads decreases by 2.

Each strike of the second type (and only it) changes the parity of the number of heads. Since the number of heads is initially odd, and in the end, it should become an even number (0), the number of strikes of the second type must be odd. However, one such strike is insufficient—it will not be enough to cut off all the tails, and strikes of other types only increase the number of tails. Therefore, there must be at least three strikes of the second type.

With this, at least three additional heads will grow, and to cut off all the heads, at least three strikes of the third type will be required.

Moreover, three strikes of the second type will cut off six tails, so at least three additional tails need to grow, which will require at least three strikes of the first type. In total, at least nine strikes are needed. And they are sufficient. For example, Ivan can first deliver three strikes of the first type (increasing the number of tails to six), then cut off all the tails with three strikes of the second type (resulting in six heads), and finally, cut off these six heads with three strikes of the third type.