Question

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

Answer 1

【答案】

【解析】

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

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

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

所以,.

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

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

由上可見, .

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

對其中任何兩個保安亭.

當屬于同一組時,.

當中恰有一個屬于中央一組時,安全區或者恰含中央一組中的一個點,或者恰含非中央一組中的一個點,所以,.

當都屬于邊界相鄰兩組時,安全區或者恰含其中一組中的一個點,或者恰含另一組中的一個點,所以,.

當都屬于邊界相對兩組時,安全區恰含這兩組中的一個點,且最多含有中央一組中的個點,所以,.

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

故.