2005 IMO Shortlist S03

This ISL 2005 problem has not been used in any TST I know. A pity, since it is a nice problem, but in its shortlist formulation, it is absolutely incomprehensible. Here is a mathematical restatement of the problem:

Let $k$ be a nonnegative integer.

A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex $v$ is called an *extended successor* of a vertex $u$ if there is a chain of vertices $u_{0}=u$ , $u_{1}$ , $u_{2}$ , ..., $u_{t-1}$ , $u_{t}=v$ with $t>0$ such that the vertex $u_{i+1}$ is a successor of the vertex $u_{i}$ for every integer $i$ with $0\leq i\leq t-1$ . A vertex is called *dynastic* if it has two successors and each of these successors has at least $k$ extended successors.

Prove that if the forest has $n$ vertices, then there are at most $\frac{n}{k+2}$ dynastic vertices.

据我所知，这个 ISL 2005 问题还没有在任何 TST 中使用过。遗憾的是，虽然这是一个很好的问题，但在其入围方案中，它绝对是不可理解的。这是该问题的数学重述：

令 $k$ 为非负整数。

森林由有根(即有向)的树木组成。森林的每个顶点要么是一片叶子，要么有两个后继者。如果存在顶点链 $u_{0}=u$ 、 $u_{1}$ 、 $u_{2}$ 、 ...、 $u_{t-1}$ 、 $u_{t}=v$ 且 $t>0$ 使得顶点 $u_{i+1}$ 是该顶点的后继，则顶点 $v$ 称为顶点 $u$ 的*扩展后继* $u_{i}$ 对于每个整数 $i$ 和 $0\leq i\leq t-1$ 。如果一个顶点有两个后继者，并且每个后继者至少有 $k$ 扩展后继者，则该顶点被称为“动态”。

证明如果森林有 $n$ 个顶点，则最多有 $\frac{n}{k+2}$ 个王朝顶点。