PUMaC 2008 · 个人决赛（A 组） · 第 2 题

PUMaC 2008 — Individual Finals (Division A) — Problem 2

A hypergraph consists of a set of vertices V and a set of subsets of those vertices, each of which is called an edge. (Intuitively, it’s a graph in which each edge can contain multiple vertices). Suppose that in some hypergraph, no two edges have exactly one vertex in common. Prove that one can color this hypergraph’s vertices such that every edge contains both colors of vertices. n a n

解析

Let P be a convex polygon, and let n ≥ 3 be a positive integer. On each side of P , erect a regular n -gon that shares that side of P , and is outside P . If none of the interiors of these regular n -gons overlap, we call P n - good . (a) Find the largest value of n such that every convex polygon is n -good. (b) Find the smallest value of n such that no convex polygon is n -good. 2 ◦ ( ANS: The angle measure of a regular n -gon is (1 − )180 . A polygon is n -good if and only if n we can fit two of these angles outside each angle of the polygon; that is, if and only if 2 ◦ ◦ 2(1 − )180 + x ≤ 360 for each angle x of the polygon. Simplifying the inequality, we have n ◦ 720 ◦ x ≤ . (a) The answer is 4. For n = 4, we have x ≤ 180 , which is certaintly true for each angle n ◦ ◦ of a convex polygon. For n = 5, we have x ≤ 144 , so no polygon with an angle larger than 144 is 5-good. (b) The answer is 13. An equilateral triangle is n -good for all 3 ≤ n ≤ 12. We now prove no polygon is 13-good. Suppose a polygon has k sides. The sum of the angles of the polygon is ◦ ( k − 2)180 2 ◦ ◦ ( k − 2)180 , so there must be some angle which measures at least = (1 − )180 . Since k k 2 2 ◦ ◦ ◦ k ≥ 3, there must be angle measuring at least (1 − )180 ≥ (1 − )180 = 60 . But the condition k 3 ◦ 720 ◦ for 13-goodness is x ≤ < 60 for all angles x , so no polygon is 13-good. CB: GL) 13