Lifshits $\underline{\text { K. }}$.

Hydras consist of heads and necks (each neck connects exactly two heads). With one sword strike, one can cut all the necks coming out of some head $A$ of the hydra. But in this case, from head $A$, one neck will instantly grow to all heads with which $A$ was not connected. Heracles defeats the hydra if he manages to cut it into two parts not connected by necks. Find the smallest $N$ such that Heracles can defeat any hundred-necked hydra by striking no more than $N$ times.
Let's move on to a graph where heads are vertices, necks are edges, and a strike on the necks coming out of head $A$ is called inverting vertex $A$.

If there is a vertex $X$ of degree no more than 10, it is sufficient to invert its neighbors, and it will separate. If there is a vertex connected to all vertices except $n$ (where $n \leq 9$), then it is necessary to first invert this vertex, and then those $n$ vertices with which it was not initially connected, and then this vertex will separate.

If, however, each vertex is connected to at least 11 and not connected to at least 10 others, then there are at least 22 vertices, and at least $22 \cdot 11 / 2 > 100$ edges.

An example of a hydra that cannot be cut with fewer than nine strikes: two groups of 10 heads and 100 necks, connecting all pairs of heads from different groups.

Note that the state of the edge between vertices $A$ and $B$ does not change if and only if vertices $A$ and $B$ are inverted an even number of times in total. Therefore, the order of cutting vertices does not matter, and it is meaningless to invert a vertex twice.

Suppose no more than nine strikes have been made on our hydra. Then in each group, there is one non-inverted head left, and therefore there is a neck from one group to the other; moreover, all non-inverted heads form a connected set. On the other hand, each non-inverted head is connected to all inverted heads in its group. Therefore, if at least one head is inverted in each part, the hydra remains connected. If all inverted heads are in one part, the hydra also remains connected: each non-inverted head in this part is connected to the entire other part and to all inverted heads.

## Answer

$N=10$.

Submit a comment