Combinatoria
Olimpiada IMO (2005)
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