« Vrati se
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.

Slični zadaci

#NaslovOznakeRj.KvalitetaTežina
1858IMO Shortlist 1993 problem C10
1859IMO Shortlist 1993 problem C22
1861IMO Shortlist 1993 problem C40
1873IMO Shortlist 1993 problem N31
2182IMO Shortlist 2005 problem C19
2184IMO Shortlist 2005 problem C35