Question 116
Numbers $m$ and $n$ are given positive integers. There are $mn$ people at a party, standing in the shape of an $m \times n$ grid. Some of these people are police officers and the rest are guests. Some of the guests may be criminals. The goal is to determine whether there is a criminal among the guests or not.
Two people are considered *adjacent* if they have a common side. Any police officer can see their adjacent people and, for every one of them, know whether they are a criminal or not. On the other hand, any criminal will threaten exactly one of their adjacent people (which is likely an officer!) with murder. A threatened officer will be so scared that they deny the existence of any criminal among their adjacent people.
Find the least possible number of officers such that they can take positions at 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.)
Two people are considered *adjacent* if they have a common side. Any police officer can see their adjacent people and, for every one of them, know whether they are a criminal or not. On the other hand, any criminal will threaten exactly one of their adjacent people (which is likely an officer!) with murder. A threatened officer will be so scared that they deny the existence of any criminal among their adjacent people.
Find the least possible number of officers such that they can take positions at 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.)