En un torneo de $n$ equipos, cada equipo juega todos otros equipos exactamente una vez, sin sorteo. Que $n$ ¿es siempre posible a todos los equipos se dividen en varios grupos para que cada grupo de equipos ganó el mismo número de juegos en total?
[Fuente: problema de competencia ucraniano]
Finalmente me creo (creo :p) que he entendido la pregunta. La palabra "torneo" no es realmente apropiado y se confunden debido a que la descripción si de una liga (partido de todos vs todos), torneos generalmente tienen estructura de árbol, lo que no es el caso aquí.
Para cualquier número de puntos en los que queremos conectar cada punto con otro por una línea esto significa que vamos a elegir las formas de 2 puntos, es decir, si el número de equipos es n el número de partidos se
$$m=\binom{n}{2}=\frac{n(n-1)}{2}$$
Podemos ver que m victorias pueden ser distribuidos en n equipos con algunas restricciones: el máximo número de victorias del equipo puede adquirir es $n-1$ y SÓLO UN equipo puede hacerlo debido a que cada equipo juega exactamente $n-1$ partidos.
Hay otra restricción: sólo un equipo puede perder todos los juegos, por la misma razón que el máximo. Así que tenemos una posible y la única máximo de victorias, que es $n-1$ y un posible y única "puro perder', es decir, cero victorias para algún equipo.
Entre el $n-1$ $0$ el m victorias puede ser distribuido en forma alguna entre los equipos.
Si puedo crear una distribución y un número impar de victorias de un equipo y de un número par de victorias de todos los demás, debe ser imposible para reorganizar los equipos en grupos con el mismo número de victorias, porque la suma de los números pares es par y la suma de un número impar, y cualquier cantidad de números impares es impar.
Una estrategia diferente será demostrar que existe alguna distribución de m con 2 o 3 tipo de número de victorias que hacen imposible reorganizar en grupos con el mismo número de victorias.
Necesito demostrar que este tipo de distribuciones existe para n posiciones y m victorias con las restricciones de un máximo de $(n-1)$ y un posible $0$.
Voy a suponer que usted puede reorganizar los equipos en grupos de diferente cardinalidad.
Si n es incluso entonces puedo demostrar que sólo $n=4$ puede ser reorganizado en grupos con el mismo número de victorias, suponiendo que se pueden crear grupos con diferente longitud.
Si n es, incluso, a continuación, $n-1$ es impar, por lo que puedo ver si resta alguna cantidad a m el resto pueden ser divididas en algunos una cantidad:
$$a=\frac{m-(n-1)}{n-1}=\frac{\frac{n(n-1)}{2}-(n-1)}{n-1}=\\ a=\frac{n-2}{2}$$
Tengo que ver ahora si $n-1$ puede ser expresada como la suma de $a$ cantidades, es decir, si $$n-1=k\cdot a=k\frac{n-2}{2}\to n=2+\frac{2}{k-2};\ k\in\Bbb N$$
Para $k=3\to n=4$ es el único caso, incluso con n donde: $n-1$ puede ser expresada como la suma de $a$.
Podemos extender este análisis de esta distribución $m_e=\{n-1,a,...,a\}$ a los casos en los que queremos ver si es posible expresar cualquier cantidad $(n-1)+k\cdot a=j\cdot a;\ k,j\in\Bbb N$. Podemos ver que esto es imposible para cualquier n con la excepción de $n=0$ o $n=1$, lo que está fuera de esta cuestión, ya que para un partido que necesitamos, por lo menos, los 2 equipos, es decir,$n>1$.
Conclusión: para cualquier otro, incluso, $n\neq 4$ existirá una distribución de la especie $m_e=\{n-1,a,a,...,a\}$ donde es imposible distribuir este m victorias en grupos con el mismo número de victorias.
Ahora podemos intentar algo similar para impar n. Debo intentar demostrar que para cada impar n existe una distribución de la especie $m_o=\{n-1,n-2,a,a,a,...,a\}$ donde $n-2$ es un número impar en esta distribución y la cantidad de $(n-1)+(n-2)$ no puede ser expresado como suma de $a$ (obviamente $(n-1)$ $(n-2)$ annot se expresa, al mismo tiempo, como múltiples $a$).
Voy a demostrar que esta $a$ existe.
$$a=\frac{m-(n-1)-(n-2)}{n-2}=\frac{n^2-5n+6}{2n-4}\n^2-n(5+2a)+6+4a=0\\ n=2a+3;\ a=\frac{n-3}{2}$$
Ahora tengo que ver si la cantidad de $(n-1)+(n-2)$ puede ser expresado en términos de $a$ Y, AL MISMO TIEMPO, esta cantidad $(n-1)+(n-2)=k\cdot a$ puede ser un múltiplo de $n-2$ de las posiciones que tienen un valor de $a$, es decir,$j\cdot a=n-2$, es decir,
$$2n-3=k\frac{n-3}{2}\to n=3+\frac{6}{k-4};\ k\in\Bbb N$$
y
$$j\cdot k\cdot a=n-2\to n=3+\frac{2}{jk-2};\ k,j\in\Bbb N$$
Para la primera fórmula podemos ver que $k\in\{1,2,3,5,6,7,10\}$ $n\in\{1,0,-3,9,6,5,4\}$ respectivamente. La única casos interesantes aquí están los impares de n, es decir,$k\in\{3,5,7\}$. Esto significa que para estos k la cantidad de $(n-1)+(n-2)=k\cdot a$.
Para cada $k$ vemos que el $j$ en la segunda fórmula conducir a una contradicción o inexistentes $j$. Así que no existe una distribución de la especie $m_o=\{n-1,n-2,a,...,a\}$ que puede expresar la cantidad de $(n-1)+(n-2)$ como sumas de $k\cdot a$ y, al mismo tiempo, esta $k\cdot a$ ser proporcional a la longitud de la $(n-2)$.
Podemos probar también que la cantidad de $(n-1)+(n-2)+a$ (recuerden $a=\frac{n-3}{2}$) no puede ser expresado como una suma de $k\cdot a$ y, al mismo tiempo, $j\cdot k\cdot a=n-3$ cualquier $j$, es decir, de ser posible dividir la distribución en este tipo de sumas. Para las grandes sumas de dinero de la especie $(n-1)+(n-2)+h\cdot a$ usted puede probar que el mismo (el único de los posibles casos de estudio se $n=5$$n=9$).
Así que esto demostrar que para cada extraño $n$ existe una distribución de la especie $m_o=\{n-1,n-2,a,a,...,a\}$ que hacen imposible distribuir estos valores en grupos con el mismo valor.
EDIT: necesito una última prueba en la distribución de $m_o$, si es posible de alguna distribución de los valores de $(n-1)+k\cdot a=(n-2)+j\cdot a=h\cdot a$ algunos $k+j+l\cdot h=n-2;\ k,j,l\in\Bbb N$$h\in\Bbb N_0$.
Podemos empezar a ver si es posible que $(n-1)+ka=(n-2)+ja\to a=\frac{1}{j-k}$. Este es el único caso con sentido donde $a=1\to n=5$. Podemos ver que la distribución de $n=5,\ m_o=\{4,3,1,1,1\}$ puede ser arreglado, efectivamente, como dos grupos de la misma cantidad de victorias, es decir,$m_o=\{4,1\}+\{3,1,1\}$.
Pero por otro lado podemos ver que la distribución de $n=5,\ m^*=\{4,0,2,2,2\}$ no puede ser reorganizado en grupos con el mismo valor en cualquier forma.
Conclusión: no existe ningún impar n que puede llevar a cualquier tipo de distribución de la misma m victorias que hacen posible reorganizar en grupos con el mismo número de victorias.
Así que el único n de que puede tener m victorias distribuidos en grupos del mismo número de victorias es $n=4$.
Para cualquier otro n existirá una distribución de la especie $m_e=\{n-1,a,...,a\}$ incluso para ny $m_o=\{n-1,n-2,a,a,...,a\}$ por extraño $n\neq 5$ que hacen imposible distribuir el m victorias en grupos con el mismo número de victorias. Y para $n=5$ tenemos la distribución de $m^*=\{4,0,2,2,2\}$ que no pueden ser agrupadas en cualquier forma válida.
P. S.: si supongo que dividimos el m victorias en grupos de la misma longitud, entonces no existe ninguna n que puede distribuir las victorias en el n de los equipos a tener grupos con el mismo número de victorias.
P. S. 2: no sé nada acerca de la teoría de grafos así que, posiblemente, mi respuesta es inesperadamente demasiado tiempo. Sry por demasiado ediciones... un montón de pequeños (algunos grandes) errores.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
