Baltic Way 2018 · Problem 8

Let hunters apply optimal (fastest) algorithm. Let say that a vertex has a smell of a hare, if there exists an initial vertex and a sequence of moves of the hare for which the hare is still alive and now occupies this vertex. After every shoot mark the set of all the vertices that have a smell of a hare. In the beginning all the vertices of the graph have a smell of hare, and after finish of hunting this set is empty. The idea is that in optimal strategy these sets can not repeat!

Indeed, the hunting does not imply feedback, the hunters' shoots do not depend on hare's moves because the hunters try to foresee all possible moves of hare. So if a set of vertices $A$ appears after the $k$-th shoot and once again after the $m$-th shoot, then the strategy is not optimal because all shoots from $k$-th to $(m-1)$-th can be omitted with the same result of hunting.

Since it is possible to mark at most $2^N$ sets the hunting will finish in at most $2^N - 1$ shoots.