King Arthur had to fight the Three-Headed and Three-Tailed Dragon (known as $D T C T C$). His task was made easier when he managed to obtain a magical sword that could deliver the following strikes (one at a time):
A) cut off one head;
C) cut off one tail;
B) cut off two heads;
D) cut off two tails.

Moreover, the Fairy Morgana revealed the dragon's secret to him:

i) if one head is cut off, a new one will grow;

ii) if two heads are cut off, no new heads or tails will grow immediately after the strike;

iii) in place of a cut tail, two new tails will grow;

iv) if two tails are cut off, a new head will grow;
v) the dragon dies if it loses all three heads and three tails.

a) Is it possible for the dragon to end up with 4 heads and 4 tails?

b) To kill the $D T C T C$, what is the minimum number of strikes King Arthur will need to deliver?
Solution

a) Yes, it is enough for the King to use, for example, the sequence of strikes $D \rightarrow C \rightarrow C \rightarrow C$.

b) From a practical standpoint, the only strike that reduces the number of heads is $B$, but we need two of them to perform it (the same applies to tails and the strike $D$), unless some strike leaves it without a head and a tail, in which case it dies before regenerating. Due to parity, the number of heads will need to increase at least once. Moreover, no strike eliminates more than 2 members, so we will need at least 3 more strikes. Below is a sequence with this minimum of $1+3=4$ strikes.

| $n$ | Strike | Head | Tail |
| :---: | :---: | :---: | :---: |
| 0 | - | 3 | 3 |
| 1 | After $D$ | 4 | 1 |
| 2 | After $B$ | 2 | 1 |
| 3 | After $B$ | 0 | 1 |
| 4 | After $C$ | 0 | 0 |

[*] Notice that when cutting the tails, as there are no more heads at the moment, the DTCTC both loses its regenerative power and dies. Therefore, 4 is the minimum number of strikes.