Un torneo $T_{n}$ en un conjunto V de n jugadores es una orientación de los bordes de un grafo completo $K_{n}$ . El nombre del torneo es natural ya que se puede pensar en el conjunto V como un conjunto de jugadores en el que cada pareja participa en un único partido, donde (x,y) está en el torneo $T_{n}$ y si x gana a y. decimos que $T_{n}$ tiene la propiedad $S_{k}$ si para cada conjunto dado de k jugadores, hay otro jugador que les gana a todos.
Pregunta: para todo k $\geq$ 1, ¿existe n y $T_{n}$ tal que $T_{n}$ tiene la propiedad $S_{k}$ ?
Propuesta: Si $\binom{n}{k}(1-\frac{1}{2^{k}})<1$ La respuesta es sí.
Comentario y prueba
-
Para k fijo, demuestre que $\lim_{n \rightarrow + \infty} \binom{n}{k}(1-\frac{1}{2^{k}})^{n-k}=0$ .
-
Vamos a ver que siempre que $n>>k$ un torneo elegido al azar es muy probable que tenga la propiedad $S_{k}$ .
(a) Sea f(k) el menor número de jugadores tal que exista un torneo $T_{f(K)}$ poseer la propiedad $S_{k}$ . Utilizando el resultado de la proposición explique por qué si $\frac{ne}{k}e^{-(n-k)/(k2^{k})}<1$ entonces $f(k)\leq n$
(b) Elija $n(k)=(In2+2\frac{In K}{k})k^{2}2^{k}$ , se deduce que para k grande, $f(k)\leq In(2)k^{2}2^{k}(1+o(1))$ .
Szekeres ('68) ha demostrado que $f(k)\geq Ck2^{k}$ ; por ejemplo, puedes comprobar por tus medios que f(1)=3 y f(2)=7.
- Pasamos a la demostración de la proposición, el número entero n es ahora fijo. Elegimos uniformemente al azar una orientación de $k_{n}$ . Para K $\in p_{k}([n])$ , dejemos que $A_{k}$ denota el evento "ningún otro jugador gana a todos los k jugadores de K '.
(a) Explique por qué para cualquier K $\in p_{k}([n]),$ P $(A_{k})=(1-\frac{1}{2^{k}})^{n-k}$ .
(b) Demuestre que P $(\bigcup_{K\in p_{k}([n])} A_{K})\leq\binom{k}{n}(1-\frac{1}{2^{k}})^{n-k}$ .
(c) Finaliza la demostración de la proposición.
