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
Problem
Source: Iranian TST 2019, second exam, day1, problem 3
Tags: combinatorics
Pathological
04.07.2019 21:49
Darn problem was edited . Anyways, here is a solution for the problem where adjacent = in the same row or column, as it's nontrivial.
The answer is $\left \lceil \frac{mn+1}{2} \right \rceil$. In other words, there must exist a strict majority of the people at the party who are officers.
It's easy to see that the officers can win in this case. For instance, simply checkerboard-color the grid such that some corner is white, and place the officers at all the white squares (and potentially one more if $mn$ is even).
Now, let's show that the officers cannot win if there are at least as many non-police as police.
Let $P$ be the set of cells which are occupied by police officers and let $C$ be the set of cells which are not.
For a subset $S \subseteq C$, let $f(S)$ be the set of cells of police officers which are adjacent to at least one cell in $S$.
Case 1. There exists a subset $S \subseteq C$ with $|f(S)| < |S|$.
Consider the smallest subset $S \subseteq C$ such that $|f(S)| < |S|.$ This must exist since $|f(C)| \le |C|.$ If $|S| = 1$, then we're clearly done, since the criminal can just threaten the corresponding officer and we win. Otherwise suppose that $|S| > 1.$ We know that $|f(S)| = |S| - 1$ since adding a criminal to $S$ cannot decrease $f(S)$.
Then, it's clear that any subset $T \subseteq S$ which satisfies $|T| = |S| - 1$ has $f(T) = f(S),$ as otherwise the minimality of $S$ would be contradicted. Select an arbitrary subset $T \subseteq S$ with $|T| = |S| - 1.$ Consider the bipartite graph where we put $T$ on the left side, $f(T)$ on the right side, and connect $a \in T$ and $b \in f(T)$ if they are in the same row or column. By the minimality of $S$, Hall's Condition is satisfied on this bipartite graph , and so there exists a perfect matching by Hall's Theorem. In other words, if we place criminals on the cells in $S$, the criminals in $T$ can threaten all police officers in $f(S)$. Hence, if $\{e\} = S / T$, then the criminal in cell $e$ is unguarded (since all police officers in $f(S)$ are scared), and the criminals win.
Case 2. There does not exist such a subset $S$.
Then, we know that since $f(C) \subseteq P$, $f(C) = P \Rightarrow |C| = |f(C)| = |P|.$ if we create a graph with $C$ on the left and $P$ on the right, then Hall's condition is satisfied on this graph. In other words, all the criminals can simply threaten all the police officers, and so they clearly win.
$\square$
Pathological
04.07.2019 22:38
Actually, I think the above proof basically works for the current version as well. The same construction works. Now, for any smaller number of policemen, they must "cover" all other cells, in the sense that any other cell must be adjacent to some police. Furthermore, any policeman must cover some non-police cell, as otherwise he's useless and we can just remove him. From here, I believe the same proof as above works .
Idio-logy
19.01.2020 23:19
The answer is $\frac{mn}{2}+1$ when $mn$ is even, and $\frac{mn+1}{2}$ when $mn$ is odd.
Checkerboard coloring (when $mn$ is odd), with an extra police when $mn$ is even. (I think the validity is not completely trivial and needs several lines to clarify, but I'm probably missing something.)
Now we prove that when the number of polices is no more than the number of non-polices, then the criminals could win. Let the set of polices be $P$ and the set of non-polices be $NP$, then $|P|\le |NP|$. Then
Pathological wrote:
For a subset $S \subseteq NP$, let $f(S)$ be the set of cells of police officers which are adjacent to at least one cell in $S$.
Let $S_0 \subseteq NP$ be the set with minimum cardinality such that $|f(S_0)| \le |S_0|$. This exists since $|f(NP)| \le |P| \le |NP|$.
Claim. $|f(S_0)| = |S_0|$.
Proof. Otherwise, $|f(S_0)| \le |S_0| - 1$. Deleting any element in $S_0$ will result in a decrease of at least one in $|f(S_0)|$, since otherwise we can get a smaller set by deleting this element. Thus for each element $s\in S_0$, we can find at least one element $f(s) \in f(S_0)$, such that $s$ is the only element in $f(s)$ that $f(s)$ is adjacent to. Notice that by definition, for any $s,t\in S_0$, $s\neq t$, $f(s)$ and $f(t)$ can't be the same. This clearly contradicts with the fact that $|f(S_0)| < |S_0|$.
Thus we can finish by using Hall's marriage theorem on $|S_0|$: for any set $T \subseteq S_0$, $|T| \le |f(T)|$, so there exists a $S_0$-saturating matching between $S_0$ and $f(S_0)$. Since they have the same cardinality, this is a matching, so one can put criminals at all $S_0$ grids and they can threaten the polices according to the matching.