IMO Shortlist 2005 problem C2

  Avg: 4,0
  Avg: 6,0
Dodao/la: arhiva
2. travnja 2012.
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.
Izvor: Međunarodna matematička olimpijada, shortlist 2005