Question

【题目】21世纪城的街道都是东西向和南北向,为了加强安全管理,在一些十字路口设置保安亭(任何两个保安亭都不在同一街道上),以两个保安亭为其两个顶点、街道为边围成的矩形称为一个安全区,安全区(包括边界)内保安亭的个数称为该安全区的安全强度.如果世纪城两个方向的街道都至少有条,且任何两条不平行的街道都交成一个十字路口,今按要求选定个十字路口设置保安亭,求安全强度最大的安全区的安全强度的最小值.

Answer 1

【答案】

【解析】

设最南、最东、最北、最西边的一个保安亭分别为(可能有重合).分别过的东西向街道与分别过的南北向街道围成一个矩形,则所有保安亭都在内.令,并用表示安全区的安全强度.

(1)若中至少有两个不同点为的顶点,则本身为安全区.此时,.

(2)若中恰有一个为的顶点(设为A).此时,的不含的两边上各有一个保安亭(设为).则三个安全区覆盖了.于是,外的个保安亭都被上述三个安全区覆盖.从而,至少有一个安全区覆盖了这个保安亭中至少个保安亭.又覆盖了中两个点(以其中两个点为顶点),

所以,.

(3)若都不是的顶点,则四个安全区覆盖了中除矩形外的所有保安亭.又安全区覆盖了矩形.于是, 外的个保安亭都被上述五个安全区覆盖.从而,至少有一个安全区覆盖了这个保安亭中至少个保安亭.

又覆盖了中两个点(以其中两个点为顶点),所以,.

由上可见, .

其次,将个保安亭分为五组,各组保安亭个数及分布如图所示,其中,边界四组中有个组含有个保安亭,其他的组都含有个保安亭.

对其中任何两个保安亭.

当属于同一组时,.

当中恰有一个属于中央一组时,安全区或者恰含中央一组中的一个点,或者恰含非中央一组中的一个点,所以,.

当都属于边界相邻两组时,安全区或者恰含其中一组中的一个点,或者恰含另一组中的一个点,所以,.

当都属于边界相对两组时,安全区恰含这两组中的一个点,且最多含有中央一组中的个点,所以,.

又显然存在保安亭,使,因此,.

故.