Track / Stage 8 / 128 of 180 #1828 of 1964

Problem 1828

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.6 Prove it Baltic Way shortlist · Baltic Way

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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.