IR-TST 2019 Problem 9

Numbers $m$ and $n$ are given positive integers. There are $mn$ people in a party, standing in the shape of an $m\times n$ grid. Some of these people are police officers and the rest are the guests. Some of the guests may be criminals. The goal is to determine whether there is a criminal between the guests or not. Two people are considered \textit{adjacent} if they have a common side. Any police officer can see their adjacent people and for every one of them, know that they're criminal or not. On the other hand, any criminal will threaten exactly one of their adjacent people (which is likely an officer!) to murder. A threatened officer will be too scared, that they deny the existence of any criminal between their adjacent people. Find the least possible number of officers such that they can take position in the party, in a way that the goal is achievable. (Note that the number of criminals is unknown and it is possible to have zero criminals.)

Proposed by Abolfazl Asadi