PUMaC 2008 · 个人决赛（B 组） · 第 5 题

PUMaC 2008 — Individual Finals (Division B) — Problem 5

Individual Finals B n − 2 n − 1

Find all pairs of positive real numbers ( a, b ) such that ≤ b bn c < for all positive integes a 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.
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. 1

解析

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. ( ANS: Suppose not. Consider a coloring of the vertices such that as few edges as possible are monochromatic, and consider one of its monochromatic edges e . Change the color of one vertex v of e . Any other vertex that contains v must also contain another vertex of e , which remains its original color, so this does not create any new monochromatic edges, but it makes e multicolored, so the coloring did not have a minimal number of monochromatic edges, contradiction. Hence the desired coloring is possible. CB: ACH) n a n