Question

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

Answer 1

【答案】

【解析】

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

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

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

所以,.

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

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

由上可見, .

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

對(duì)其中任何兩個(gè)保安亭.

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

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

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

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

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

故.