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

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

Individual Finals A

Find all positive real numbers b for which there exists a positive real number k such that n − k ≤ b bn c ≤ n for all positive integers n .
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
A sequence { a } is defined by a = c for some c > 0 and a = a + . Prove that converges i 1 n +1 n a n n and find its limit. 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