Iranian Mathematical Olympiad

Answer. $\lfloor \frac{mn}{2}\rfloor +1$.

There are two steps for the proof, first showing that this number is enough, and for any smaller number of officers, show a way for some of the guests to be criminals and to threaten the officers such that the existence of the criminals remains unknown.

For the first part, consider two cases:

$mn$ is an odd number.

Consider the coloring of the grid with two colors, such that no two adjacent nodes are of the same color. Place the $\left[\frac{mn}{2}\right]+1$ officers on the places that have the majority color. Since any criminal can threaten exactly one person (which in this case, is definitely an officer), and since the number of officers is greater than the number of the guests (and so, greater than the number of criminals), if there exists a criminal between the guests, there will be an officer, adjacent to a criminal, whom is not threatened and can identify the criminal.

$mn$ is an even number.

Without loss of generality, assume that $n$ is an even number. Consider the same coloring of the nodes of the grid. Again, $\frac{mn}{2}$ of the officers can take position at the nodes with the majority color, and the last officer can take position at an arbitrary node with the opposite color. Similar to the previous case, since the number of officers is greater than the largest possible number of criminals, one officer will be able to identify a criminal, if there's any.

Now for the second part, consider a group of people such that the number of police officers is not greater than half of the total. It suffices to show a way for some of the guests to be criminals and to threaten the officers such that the officers will fail to reach the goal.

Construct a graph with $mn$ vertices, each vertex representing a person in the party. Partition the nodes of the graph into two sections $A$ and $B$, where every node in $A$ represents a police officer and every node in $B$ represents a guest. Construct an edge, connecting a node from $A$ to a node from $B$ if the people they represent are adjacent in the party.



The assumption is that $|A|\le |B|$. Also, any node in $B$ is connected to at least another node in $A$, because otherwise, it suffices for the person representing this node to be a criminal; Officers would not be able to identify this person.

It suffices to prove that there exists a non-empty subset of the vertices of $A$, like $X$ such that there is a matching between the vertices of $X$ and the vertices of a subset of $B$, like $Y$, and the vertices of $Y$ are not connected to any other node outside of $X$.

If the graph contains a matching, including all the vertices of $A$, the desired claim is concluded; Otherwise, according to Hall's Theorem, there exists a subset $S$ of $A$, such that the number of the vertices of $B$ that are connected to a node of this subset, is less than the number of the vertices of $S$ itself. Without loss of generality, let $S$ be the largest subset with the described property. Let $N(S)$ be the subset of the nodes of $B$ that are connected to some vertex of $S$.



If vertices of both $S$ and $N(S)$ are removed, the assumptions of Hall's theorem holds true. Because if there is a subset of $A/S$ like $S^{\prime }$ where the number of the nodes of $B/N(S)$ are less than the number of the vertices of $S^{\prime }$, then $S\cup S^{\prime }$ in $A$ has the same described property as $S$, thus $S$ could not be the largest subset with that property. Now, considering the complete matching between the nodes of this new graph, the claim is concluded; Because the nodes of $B/N(S)$ are not connected to any node outside of $A/S$. Note that $A\ne S$, because all vertices of $B$ have the degree of at least one, and also $|A|\le |S|$. Therefore the given number is proved to be the correct answer. $\square$

Therefore the given number is proved to be the correct answer. $■$