En un torneo de tenis participan por lo menos [math]3 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]A,B,C tales que [math]A le gana a [math]B, [math]B le gana a [math]C y [math]C le gana a [math]A.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Sea [math]n la cantidad de jugadores [math]a_1, a_2, \ldots, a_n. Sea [math]k la cantidad de partidos que ganó el que menos partidos ganó (o uno de los que menos partidos ganó). Sea [math]a_i un jugador que ganó [math]k partidos.
Si [math]k=1, [math]a_i ganó un solo partido. Pongamos que [math]a_j sea el único que perdió contra [math]a_i. Entonces hay [math]n-2 jugadores que le ganaron a [math]a_i. Si [math]a_j le gana a alguno de esos [math]n-2 jugadores, estamos listos. Supongamos, por el contrario, que [math]a_j pierde contra los [math]n-2 que le ganaron a [math]a_i, como [math]a_j perdió contra [math]a_i entonces se tiene que [math]a_j perdió contra todos. Absurdo, pues cada jugador ganó, al menos, un partido.
Por inducción en [math]k, supongamos que es cierto hasta cierto valor, digamos [math]r. Veamos qué pasa con [math]k=r+1.
Sea, nuevamente, [math]a_i el jugador que ganó [math]r+1 partidos. Entonces existen [math]n-r-2 jugadores que le ganaron a [math]a_i y [math]r+1 que perdieron contra [math]a_i. Sean [math]a_{j_1}, \ldots , a_{j_{r+1}} los que perdieron contra [math]a_i. Si algún [math]a_j_k le ganó a alguno de los [math]n-r-2 jugadores que le ganaron a [math]a_i, estamos listos. Supongamos que no, entonces los [math]r+1 jugadores que perdieron contra [math]a_i, se ganaron entre sí. Es claro que cada uno de estos jugadores ganó al menos [math]r+1 partidos. Pero tiene [math]r rivales a los cuales les puede ganar. Entonces, algún [math]a_j_k le ganó a alguno de los [math]n-r-2 jugadores que le ganaron a [math]a_i, y por lo tanto existe una terna como la que propone el enunciado.
Sea [math]\theta = 1,3063778838... Para todo entero positivo [math]k se cumple que [math]\left\lfloor \theta^{3^k}\right\rfloor es un número primo.
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.
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]A, [math]B, y [math]C. (1)
Ahora supongamos que con n+1 no existen [math]A, [math]B, y [math]C, 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]A, [math]B, y [math]C. ABSURDO.
Luego existen [math]A, [math]B, y [math]C, para n+1.
Con 3 participantes es trivial que existen los tres participantes, luego por induccion, se puede para todo n.
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.
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.
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]k, existen [math]k primos en sucesión aritmética.
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 $d^+(v)$ de cada vértice $v$ cumple que $d^+(v)\geq 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 $d^+(v_n)\geq 1$ y existe $(v_{n-1},v_n)$, tenemos que existe $(v_n,v_i)$ para algún $1\leq i\leq 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$.
