34 T. I. de las Ciudades Primavera 2012 N Juvenil Problema 7

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nacho

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

34 T. I. de las Ciudades Primavera 2012 N Juvenil Problema 7

Mensaje sin leer por Nacho » Jue 14 Mar, 2013 4:54 pm

Dos equipos, [math] y [math] juegan un torneo de ping-pong. El equipo [math] tiene [math] integrantes y el equipo [math] tiene [math] integrantes, con [math]. Hay una sola mesa de ping-pong y el torneo se organiza de la siguiente manera: Dos integrantes de distintos equipos comienzan a jugar, mientras que los otros jugadores forman una fila, esperando su turno para jugar. Después de cada partido, el primer jugador de la fila reemplaza al miembro de su mismo equipo y juega con el otro jugador (que ya había jugado el partido anterior). El jugador que fue reemplazado se coloca al final de la fila. Demostrar que cada par de integrantes de equipos opuestos en algún momento jugarán uno contra el otro. (9 puntos)
"Though my eyes could see I still was a blind man"

Joacoini

OFO - Medalla de Plata
Mensajes: 28
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 1
Nivel: 2

Re: 34 T. I. de las Ciudades Primavera 2012 N Juvenil Problema 7

Mensaje sin leer por Joacoini » Dom 08 Abr, 2018 10:21 am

Solución Oficial
Spoiler: mostrar
Numeramos por separado los jugadores de los dos equipos por su orden en la fila original: $a_1,..., a_m$ y $b_1,..., b_n$. El primer juego es entre $a_1$ y $b_1$. Observamos que a lo largo del torneo los jugadores del mismo equipo (incluyendo al que en ese momento está jugando) preservan su orden cíclico en la fila. Un jugador de un equipo puede cambiar su posición relativa con respecto a un jugador del otro equipo y esto solo puede ocurrir en la mesa de ping pong: un jugador puede entrar a la mesa antes que el jugador del otro equipo y dejar la mesa después que éste.
Dividimos los partidos en series de $m+n-2$ partidos cada una. Durante la primera serie todos los primeros $m+n-2$ jugadores, excepto $a_m$ y $b_n$ jugarán en la mesa. Los dos jugadores mencionados jugarán su primer partido en la segunda serie. De modo similar, $a_{m-1}$ y $b_{n-1}$ serán los que jugarán su primer partido en la tercera serie, y así siguiendo. Vemos que cada vez los índices de cada jugador en su primer partido de la serie se mueven un lugar hacia atrás, en un ciclo.
Esto implica que en $m$ series cada integrante del equipo $A$ dejará la mesa exactamente $m-1$ veces y en $n$ series, cada integrante del equipo $B$ dejará la mesa exactamente $n-1$ veces. Luego, en $mn$ series los números de jugadores de los equipos $A$ y $B$ que dejan la mesa serán exactamente $n(m-1)$ y $m(n-1)$, respectivamente.
Sea $m>n$. Entonces $n(m-1)-m(n-1)=m-n\geq 1$. Consideramos jugadores arbitrarios $a_i$ y $b_j$. Al cabo de $2mn$ series $a_i$ deja la mesa al menos 2 veces más que $b_j$. Entonces habrá dos salidas consecutivas de $a_i$ tales que mientras tanto $b_j$ permanece en la fila (sin entrar a jugar). Si suponemos que $a_i$ y $b_j$ no se enfrentan, $a_i$ debe sobrepasar a $b_j$ en la fila, lo cual es imposible.
Tetraedro inscripto en un paralelepípedo contiene un tercio del volumen de este.

Responder