Question

【題目】21世紀(jì)城的街道都是東西向和南北向,為了加強(qiáng)安全管理,在一些十字路口設(shè)置保安亭(任何兩個保安亭都不在同一街道上),以兩個保安亭為其兩個頂點(diǎn)、街道為邊圍成的矩形稱為一個安全區(qū),安全區(qū)(包括邊界)內(nèi)保安亭的個數(shù)稱為該安全區(qū)的安全強(qiáng)度.如果世紀(jì)城兩個方向的街道都至少有條,且任何兩條不平行的街道都交成一個十字路口,今按要求選定個十字路口設(shè)置保安亭,求安全強(qiáng)度最大的安全區(qū)的安全強(qiáng)度的最小值.

Answer 1

【答案】

【解析】

設(shè)最南、最東、最北、最西邊的一個保安亭分別為(可能有重合).分別過的東西向街道與分別過的南北向街道圍成一個矩形,則所有保安亭都在內(nèi).令,并用表示安全區(qū)的安全強(qiáng)度.

(1)若中至少有兩個不同點(diǎn)為的頂點(diǎn),則本身為安全區(qū).此時,.

(2)若中恰有一個為的頂點(diǎn)(設(shè)為A).此時,的不含的兩邊上各有一個保安亭(設(shè)為).則三個安全區(qū)覆蓋了.于是,外的個保安亭都被上述三個安全區(qū)覆蓋.從而,至少有一個安全區(qū)覆蓋了這個保安亭中至少個保安亭.又覆蓋了中兩個點(diǎn)(以其中兩個點(diǎn)為頂點(diǎn)),

所以,.

(3)若都不是的頂點(diǎn),則四個安全區(qū)覆蓋了中除矩形外的所有保安亭.又安全區(qū)覆蓋了矩形.于是, 外的個保安亭都被上述五個安全區(qū)覆蓋.從而,至少有一個安全區(qū)覆蓋了這個保安亭中至少個保安亭.

又覆蓋了中兩個點(diǎn)(以其中兩個點(diǎn)為頂點(diǎn)),所以,.

由上可見, .

其次,將個保安亭分為五組,各組保安亭個數(shù)及分布如圖所示,其中,邊界四組中有個組含有個保安亭,其他的組都含有個保安亭.

對其中任何兩個保安亭.

當(dāng)屬于同一組時,.

當(dāng)中恰有一個屬于中央一組時,安全區(qū)或者恰含中央一組中的一個點(diǎn),或者恰含非中央一組中的一個點(diǎn),所以,.

當(dāng)都屬于邊界相鄰兩組時,安全區(qū)或者恰含其中一組中的一個點(diǎn),或者恰含另一組中的一個點(diǎn),所以,.

當(dāng)都屬于邊界相對兩組時,安全區(qū)恰含這兩組中的一個點(diǎn),且最多含有中央一組中的個點(diǎn),所以,.

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

故.