Selectivo de IMO 2011 - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Mijail
Mensajes: 16
Registrado: Mié 11 Oct, 2017 9:56 pm
Nivel: 3
Ubicación: Peru, Lima

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Mijail » Dom 05 Ene, 2020 9:27 pm

Spoiler: mostrar
Voy a realizar una induccion en el problema respecto al numero de jugadores, es trivial ver que el problema cumple cuando hay solo 3 personas luego supongamos que el problema cumple para $n=3,...,k$ vamos a probar que $n=k+1$ tambien cumple.
Escojamos cualquier persona de las $k+1$ esta ser $v_1$ ahora si todas las personas con las que se enfrenta $v_1$ son derrotadas por esta solo aplicamos la induccion para $n=k$ en las personas restantes (el conjunto de todas las personas sin contar a $v_1$); ahora si llamamos a $A$ el conjunto de todas las personas derrotadas por $v_0$ y $B$ como el conjunto de todas las personas que vencieron a $v_0$, tenemos que si existe una persona $x$ en $A$ que gano a alguna persona $y$ en $B$ hemos terminado ya que tomamos a las personas $v_1$ , $x$ e $y$ con esto encontramos la tripla que nos pide el problema. Luego si esto no sucede entonces todas las personas en $A$ perdieron con todas las personas en $B$, con esto luego aplicamos la induccion en $A$ y terminamos. :mrgreen:

Nota: Es claro que $A$ no es vacio por la condicion que al menos una persona es derrotada por $v_1$ y tampoco la cantidad de elementos de A puede ser $1$ o $2$ ya que esto contradice la condicion: cada jugador gana al menos uno de los partidos que juega.

Responder