Q8 Matemática  (IMO Shortlist 2005)

Este problema do ISL 2005 não foi usado em nenhum TST que eu conheça. Uma pena, pois é um problema legal, mas em sua formulação de shortlist, é absolutamente incompreensível. Aqui está uma reformulação matemática do problema: Seja $k$ um inteiro não negativo. Uma floresta consiste em árvores enraizadas (ou seja, orientadas). Cada vértice da floresta é uma folha ou tem dois sucessores. Um vértice $v$ é chamado de sucessor estendido de um vértice $u$ se houver uma cadeia de vértices $u_0=u$, $u_1$, $u_2$, ..., $u_{t-1}$, $u_t=v$ com $t>0$ tal que o vértice $u_{i+1}$ é um sucessor do vértice $u_i$ para todo inteiro $i$ com $0\le i\le t-1$. Um vértice é chamado dinástico se tiver dois sucessores e cada um desses sucessores tiver pelo menos $k$ sucessores estendidos. Prove que se a floresta tem $n$ vértices, então existem no máximo $\frac{n}{k+2}$ vértices dinásticos.