Olimpiada IMO 2005 Problema 2

Sea $k$ un entero no negativo. Un bosque consiste en árboles enraizados (i. e. orientados). Cada vértice del bosque es una hoja o tiene dos sucesores. Un vértice $v$ se llama un sucesor extendido de un vértice $u$ si hay una cadena de vértices $u_{0}=u$ , $u_{1}$ , $u_{2}$ , ..., $u_{t-1}$ , $u_{t}=v$ con $t>0$ tal que el vértice $u_{i+1}$ es un sucesor del vértice $u_{i}$ para cada entero $i$ con $0\leq i\leq t-1$ . Un vértice se llama dinástico si tiene dos sucesores y cada uno de estos sucesores tiene al menos $k$ sucesores extendidos. Demostrar que si el bosque tiene $n$ vértices, entonces hay a lo sumo $\frac{n}{k+2}$ vértices dinásticos.

8

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados