Baltic Way shortlist

Question

An invisible hare occupies one of N vertices of a graph G. Several hunters try to kill the hare. Each minute all of them simultaneously shoot: each hunter shoots to a single vertex, they choose the target vertices cooperatively. If the hare was in the target vertex during a shoot, the hunting is finished. Otherwise the hare can jump to one of the neighbouring vertices or stay in its vertex. The hunters know an algorithm that allows to kill the hare by at most N! shoots. Prove that then there exists an algorithm that allows to kill the hare by at most 2^N shoots.

Accepted Answer

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.