Selectivo de IMO 2011 - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 934
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Matías V5 » Jue 28 Abr, 2011 9:55 pm

En un torneo de tenis participan por lo menos [math] jugadores. Cada uno juega exactamente un partido contra cada uno de los demás. Además, cada jugador gana al menos uno de los partidos que juega. (En tenis no hay empates.)
Demostrar que en el torneo hay (al menos) tres jugadores [math] tales que [math] le gana a [math], [math] le gana a [math] y [math] le gana a [math].
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Vladislao » Vie 29 Abr, 2011 12:50 pm

Spoiler: mostrar
Sea [math] la cantidad de jugadores [math]. Sea [math] la cantidad de partidos que ganó el que menos partidos ganó (o uno de los que menos partidos ganó). Sea [math] un jugador que ganó [math] partidos.

Si [math], [math] ganó un solo partido. Pongamos que [math] sea el único que perdió contra [math]. Entonces hay [math] jugadores que le ganaron a [math]. Si [math] le gana a alguno de esos [math] jugadores, estamos listos. Supongamos, por el contrario, que [math] pierde contra los [math] que le ganaron a [math], como [math] perdió contra [math] entonces se tiene que [math] perdió contra todos. Absurdo, pues cada jugador ganó, al menos, un partido.

Por inducción en [math], supongamos que es cierto hasta cierto valor, digamos [math]. Veamos qué pasa con [math].

Sea, nuevamente, [math] el jugador que ganó [math] partidos. Entonces existen [math] jugadores que le ganaron a [math] y [math] que perdieron contra [math]. Sean [math] los que perdieron contra [math]. Si algún [math] le ganó a alguno de los [math] jugadores que le ganaron a [math], estamos listos. Supongamos que no, entonces los [math] jugadores que perdieron contra [math], se ganaron entre sí. Es claro que cada uno de estos jugadores ganó al menos [math] partidos. Pero tiene [math] rivales a los cuales les puede ganar. Entonces, algún [math] le ganó a alguno de los [math] jugadores que le ganaron a [math], y por lo tanto existe una terna como la que propone el enunciado.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

cogo

Colaborador OFO - Jurado
Mensajes: 31
Registrado: Vie 29 Oct, 2010 9:24 pm
Medallas: 2

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por cogo » Sab 30 Abr, 2011 4:28 pm

Spoiler: mostrar
Primero que nada es fácil ver que para n=3 se encuentra una terna como la del enunciado.
Supongamos ahora como hipótesis inductiva que para k jugadores hay una terna como la del enunciado.
Vamos a demostrar que entonces para k+1 jugadores encontramos una terna como la del enunciado. Supongamos a modo de contradicción que no hay una terna como la del enunciado para k+1 jugadores.
En efecto, veamos que cada jugador debe perder al menos un partido pues, de lo contrario, si un jugador gana todos los partidos tendremos k jugadores en las mismas condiciones que en un torneo con k jugadores por lo que, por la hipótesis inductiva, encontraremos la terna buscada. Luego, cada jugador debe perder al menos un partido.
Sea A el jugador que más partidos ganó (o al menos uno de los que ganó mas partidos).
Como cada jugador juega k partidos y en total se juegan (k+1)*k/2 partidos A debe ganar al menos k/2 partidos.
Sean b1, b2, ..., bt con t >= k/2 los jugadores que perdieron con A y sean c1, c2, ..., cq con q <= k/2 los jugadores que le ganaron a A. Veamos que cada uno de los ci debe ganarle a cada uno de los bj pues de lo contrario tendríamos la terna A--G-- bj --G-- ci --G-- A.
Pero entonces como cada uno de los ci le gana a cada uno de los bj y como además cada uno de los ci le gana a A cada uno de los ci ganará más partidos que A por lo que ésto se contradice con nuestra definición de A como el jugador que más partidos gana en el torneo.

Avatar de Usuario
amcandio

Colaborador
Mensajes: 312
Registrado: Sab 16 Oct, 2010 12:50 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Posadas, Misiones
Contactar:

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por amcandio » Mié 11 May, 2011 10:20 pm

Spoiler: mostrar
Supongmos que para todo numero m entre 3 y n, se cumple que para cada torneo de tenis todos contra todos de m personas, tales que uno le gano a al menos uno de los otros, se cumple con la existencia de [math], [math], y [math]. (1)

Ahora supongamos que con n+1 no existen [math], [math], y [math], entonces tomamos a un participante, digamos X y dividimos a el resto de los participantes en Y, que contiene a todos los que le ganaron a X, y en Z, que contiene a todos los que perdieron contra X. Ninguno de los de Z le pueden ganar a los de Y, entonces tiene mas de 2 personas, y se cumple que cada uno de los de Z le gana a por lo menos uno de los de Z, jugando una vez con cada uno. Como Z tiene entre n y 3 elementos sigue por (1) que existen [math], [math], y [math]. ABSURDO.
Luego existen [math], [math], y [math], para n+1.

Con 3 participantes es trivial que existen los tres participantes, luego por induccion, se puede para todo n.
"Prillo es el Lanata de la trigonometria"

sebach

Colaborador OFO - Medalla de Bronce
Mensajes: 143
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 3
Nivel: Exolímpico

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por sebach » Mié 11 May, 2011 11:52 pm

Una simple:
Spoiler: mostrar
DIgamos que el jugador que menos partidos gana, A, gana X partidos. Luego, agarramos a una de estas X personas, ya que X>0 siempre, y decimos que esta persona debe ganarle a por lo menos X personas, ya que la otra persona con X ganados era la que menos partidos gano. Como debe ganarle a X personas al menos, les puede ganar a todos los que le ganó A, pero ahi hay X-1, y entonces debe ganarle a alguna de las otras personas. Pero todo el resto de las personas le gano a A. Entonces tenemos el trio que buscabamos.
ACLARACION: Si no hubiera otra persona aparte de A y de estas X personas, entonces A les gano a todos, pero era el que menos partidos habia ganado. Entonces sí o sí hay por lo menos otro jugador.
1  

Avatar de Usuario
amcandio

Colaborador
Mensajes: 312
Registrado: Sab 16 Oct, 2010 12:50 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Posadas, Misiones
Contactar:

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por amcandio » Jue 12 May, 2011 1:21 pm

me gusta, la mia es una bosta, xD pero fue la primera que se me ocurrio
"Prillo es el Lanata de la trigonometria"

Alejo

OFO - Medalla de Plata OFO - Jurado
Mensajes: 76
Registrado: Dom 01 Abr, 2012 4:14 pm
Medallas: 3
Nivel: Exolímpico

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Alejo » Mar 30 Abr, 2013 10:16 am

Spoiler: mostrar
Decimos que para dos jugadores A y B, A>B si A le ganó a B. Supongamos que no se cumple lo que hay que demostrar. Entonces si tomamos tres jugadores A, B y C tales que A>B y B>C, entonces no se cumple que C>A, luego A>C. Con esto se ve que la relación > es una relación de orden estricta y total:
a) Para todo A no se cumple que A>A: verdadero porque A no juega consigo mismo.
b) Si A>B entonces no se cumple B>A: verdadero porque los jugadores solo juegan una vez entre sí y no pueden ganar y perder al mismo tiempo.
c) Si A>B y B>C entonces A>C: es lo que probamos en el párrafo anterior.
d) Para A y B distintos se cumple A>B o B>A: verdadero porque todos los jugadores juegan entre sí y no hay empate.
Entonces el conjunto de todos los jugadores está totalmente ordenado. Como es finito, tiene un mínimo; ese mínimo, por definición es menor a todos los demás, luego no le ganó a nadie, absurdo. Queda demostrado.

Avatar de Usuario
julianferres_

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por julianferres_ » Jue 19 Dic, 2013 6:22 pm

Selectivo IMO 2011 P5.pdf
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata
Mensajes: 408
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Violeta » Jue 03 May, 2018 7:57 am

Spoiler: mostrar
Diremos que los jugadores $a_1,a_2, \ldots , a_k$ están en un ciclo de tamaño $k$ si $a_i$ le ganó a $a_{i+1}$, tomando los índices $\pmod{k}$.

Primero, como cada jugador le ganó a por lo menos un jugador, y no hay empates, definitivamente hay un ciclo entre los jugadores. Digamos que de todos los posibles ciclos, el más pequeño tiene tamaño $k \neq 3$, para probarlo por contradicción.

Luego, $a_1$ debe haberle ganado a $a_3$, porque sino habría un ciclo de tamaño tres: $a_1,a_2,a_3$. Pero entonces $a_1, a_3, \ldots , a_k$ es un ciclo de menor tamaño. Absurdo porque habíamos dicho que el de menor tamaño tiene tamaño $k\neq 3$. Entonces, el ciclo más pequeño tiene tamaño $3$ y estamos.
Para todo [math], existen [math] primos en sucesión aritmética.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1123
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de IMO 2011 - Problema 5

Mensaje sin leer por Gianni De Rico » Jue 02 Ene, 2020 12:11 pm

Solución:
Spoiler: mostrar
Sea $n$ la cantidad de jugadores. Consideramos el grafo dirigido $G$ en el que los vértices son los jugadores, y para cada par de vértices $u,v$, existe la arista $(u,v)$ si y sólo si $u$ le ganó a $v$. Como cada jugador ganó al menos un partido, el grado de salida $\delta ^+(v)$ de cada vértice $v$ cumple que $\delta ^+(v)\geqslant 1$, y como cada jugador juega exactamente un partido contra cada uno de los demás, $G$ es simple y completo, y al ser dirigido, es un torneo. Luego, tiene un camino hamiltoniano dirigido, sea $v_1,\ldots ,v_n$ dicho camino, como $\delta ^+(v_n)\geqslant 1$ y existe $(v_{n-1},v_n)$, tenemos que existe $(v_n,v_i)$ para algún $1\leqslant i\leqslant n-2$, es decir, $v_i,\ldots ,v_n$ es un ciclo, y como $G$ es un torneo, esto implica que contiene un ciclo de tamaño $3$. Luego, existen tres vértices $A,B,C$ tales que $(A,B),(B,C),(C,A)$ son aristas de $G$, y por la definición de $G$, tenemos que exiten $3$ jugadores $A,B,C$ tales que $A$ le gana a $B$, $B$ le gana a $C$ y $C$ le gana a $A$.
Queda Elegantemente Demostrado

Responder