Chvatal 博物馆定理解答

constant

一个 n 边形的博物馆要布置警卫。这些警卫不能随意走动，但可以转动。证明最多 [n/3] 个警卫就可以同时看到博物馆的所有角落。
 
引理：任意 n 边形可以剖分成 n-2 个三角形，使得每个三角形的边都是该 n 边形的边或对角线，并且 n 边形的 n 个顶点可以染成三种颜色，使得每个三角形的顶点都是不同颜色。

用归纳法。任取 n 边形的一条对角线，将 n 边形分成一个 m 边形和一个 k 边形，m + k = n + 2。 m 边形和 k 边形可以分别染成满足上述条件的颜色。然后在对角线处再把 m 边形和 k 边形接起来。（必要时调整颜色使得在对角线处颜色相同。）

现在证明定理。三种颜色的顶点中至少有一种不多于 [n/3] 个。（3 *（[n/3] + 1）> n 。）在这种颜色的每个顶点处布置一个警卫就可以同时看到所有三角形，即整个 n 边形。

www.ddhw.com

 

husonghu

   Beautiful!!