问题

考虑一个有 m 行, n 列个通道的超级市场或展览馆, 如图所示.为了防止丢失商品, 需要安排保安看守. 但是每个保安只能看守其前方和左右方, 共 3 个方向. 问: 至少需要多少个保安,才能看守所有通道?

建模

我们可将行通道与列通道抽象为线, 有 $m$ 行 $n$ 列个通道的超级市场或展览馆视为有 $m$ 条横线和 $n$ 条竖线的网格:

记最少的保安数为 $B(m, n)$ 且不妨假设 $m \geqslant n \geqslant 2$, 我们首先研究最少保安数 $B(m, n)$ 的下界. ${ }^{[46]}$ 命题 1 (下界 1) : $m$ 是 $B(m, n)$ 的一个下界,即 $B(m, n) \geqslant m$. 证明 因为一个保安不能看守属于不同行、不同列的通道. 又由 $m \geqslant n \geqslant 2$, 所以必有 $B(m, n) \geqslant m$. 命题 2 (下界 2$): \frac{2}{3}(m+n-2)$ 是 $B(m, n)$ 的另一个下界, 即 $B(m, n) \geqslant \frac{2}{3}(m+$ $n-2)$. 证明 因为一个保安如果位于外边上, 则可以看守两条线. 如果位于内部, 则只能看守 一条半线. 但是, 如果一条外边上有多个保安, 则平均每个保安至多可以看守一条半线. 因 此, 至多有四个保安每人可以看守两条线, 其余保安每人至多看守一条半线, 即有 $$ B(m, n) \geqslant 4+\frac{m+n-8}{\frac{3}{2}}=\frac{2}{3}(m+n-2) $$ 下面我们构造安排, 以求得 $B(m, n)$ 的上界, 从而确定它的值.

情况 $1 \quad m \geqslant 2 n$. 当 $m \geqslant 2 n$ 时, 先在每列上安排两个保安, 面对面站立. 而且, 这 $2 n$ 个保安位于不同的 行. 于是,他们可以看守所有的列和 $2 n$ 行. 再用 $m-2 n$ 个保安看守剩下的行. 于是共用 $m$ 个 保安看守住了所有的行和列, 从而有 $B(m, n) \leqslant m$. 结合下界 1 , 得到 情况 $24 \leqslant n \leqslant m<2 n$. $$ B(m, n)=m, m \geqslant 2 n $$ 将第 $i$ 行, 第 $j$ 列的交叉点记作位置 $(i, j)$, 先在位置 $(1,2),(2, n),(m-1,1),(m, n-$ 1) 各安排一个保安. 共四个保安看守靠近外边的 4 行和 4 列, 还剩下 $m-4$ 行与 $n-4$ 列. 于是, 又有两种情况. 情况 2 (1) $2 n-4 \leq m<2 n(4 \leq n)$. 此时剩下的行数不小于列数的二倍. 于是归结为情况 1 中的方法安排保安, 用 $m-4$ 个 保安即可. 共用 $m$ 个保安看守住了所有的行和列. 于是, 有 $B(m, n) \leqslant m$. 结合下界 1 , 此时仍 有 $B(m, n)=m$. 情况 2(2) $4 \leqslant n \leqslant m \leqslant 2 n-4$. 任取剩下的 2 行 1 列, 安排两个保安面对面站立看守. 重复这个步骤, 直到行数比列数少 1. 然后任取㔈下的 1 行 2 列, 再任取剩下的 2 行 1 列, $\cdots \cdots$, 如此交替进行 (设一共这样进行 $了 p$ 次, 用了 $2 p$ 个保安看守行或列共 $3 p$ 条线). 直到出现下面三种情况之一.

(i) 没有行或列剩下. 此时有 $3 p=(m+n-8)$. 共用保安人数为 $$ \begin{gathered} 4+2 p=\frac{2}{3}(m+n-2) \\ B(m, n) \leqslant \frac{2}{3}(m+n-2) \end{gathered} $$ 结合下界 2 , 此时有 $$ B(m, n)=\frac{2}{3}(m+n-2) $$ (ii) 没有行但剩下 1 列. 此时有 $3 p=(m+n-9)$. 剩下的 1 列要用一个保安看守. 共用保安人数为 $$ 4+2 p+1=\frac{2}{3}(m+n)-1 $$ 而下界 2 可以写作 $$ \frac{2}{3}(m+n)-1-\frac{1}{3} $$ 因为 $B(m, n)$ 是整数, 所以此时下界 2 又可以换成 $$ B(m, n) \geqslant \frac{2}{3}(m+n)-1 $$ 于是,此时 $$ B(m, n)=\frac{2}{3}(m+n)-1 $$ (iii) 剩下1 行 1 列.

此时有 $3 p=(m+n-10)$. 剩下的 1 行 1 列要用两个保安面对面站立看守. 共用保安人 数为 $$ 4+2 p+2=\frac{2}{3}(m+n-1) $$ 而下界 2 可以写作 $$ \frac{2}{3}(m+n-1)-\frac{2}{3} $$ 因为 $B(m, n)$ 是整数, 所以此时下界 2 又可以换成 $$ B(m, n) \geqslant \frac{2}{3}(m+n-1) $$ 于是,此时有 $$ B(m, n)=\frac{2}{3}(m+n-1) $$ 情况 2(2) 的(i)，(ii)，(iii) 可统一写为 $$ B(m, n)=\left[\frac{2}{3}(m+n-2)\right], 4 \leqslant n \leqslant m<2 n-4 $$ 其中 $[x]$ 表示不小于 $x$ 的最小整数. 情况 3 剩下的情况只有 $n=2, m=2,3$ 与 $n=3, m=3,4,5$. 此时, 不难证明 $$ B(m, 2)=B(m, 3)=m $$ 综合情况(i),（ii),(iii),得最终结果为 $$ B(m, n)=\left\{\begin{array}{l} {\left[\frac{2}{3}(m+n-2)\right], 4 \leqslant n \leqslant m<2 n-4} \\ m, n \text { 其他情况 } \end{array}\right. $$ 其中 $[x]$ 表示不小于 $x$ 的最小整数.

摘自