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

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

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

解析

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 . 1 Individual Finals ( ANS: The answer is 1. Let b = q + r , where q is an integer and 0 ≤ r < 1. Then b bn c = qn + b rn c . Suppose q = 0. Letting r = 1 − s , where 0 < s ≤ 1, we have rn = n − sn . For sufficiently large n , we can make sn larger than any k , so there are no solutions for q = 0. Now suppose q ≥ 1. The inequality qn + b rn c ≤ n becomes ( q − 1) n + b rn c ≤ 0. Both terms on the left hand side are nonnegative, so this can only be true if both are 0 for all n ; that is q = 1 and r = 0. CB: GL)