Demostrar que no hay dos equipos en un torneo que ganen el mismo número de partidos

Question

Supongamos que tenemos un torneo con $93$ equipos. Y entre cada $19$ equipos, hay un equipo que ha perdido todos sus $18$ juegos a otros equipos, y hay un equipo que ha ganado todos sus $18$ partidos contra los otros equipos. Entre todos los equipos, hay un partido y los únicos resultados posibles para un partido son ganar y perder.

Mi propia idea es intentar dar una prueba por contradicción, asumiendo que dos equipos comparten el mismo número de partidos ganados.

Answer 1

Definición elemento superior/inferior: En un conjunto $S$ un equipo es el mejor elemento si ha ganado contra todos los demás. Es el último si ha perdido contra todos los demás.

Definición: Digamos que un conjunto de equipos es $k$ absoluto si todo subconjunto de tamaño $k$ de estos equipos tiene un elemento superior y otro inferior.

Para probar: Usted quiere demostrar que sus equipos forman un orden total en términos de la relación ganar/perder. Aquí hay una prueba general de que existe un orden total para cualquier $n$ equipos que son $k$ absoluto siempre que $n \geq 2k > 4$ . En su caso, $n, k$ son $93, 19$ respectivamente, ajustándose a la desigualdad anterior.

Prueba: Suponga que tiene $n \geq 2k$ nodos. Podemos demostrar que forman un orden total de la siguiente manera. Quitamos el nodo superior para obtener un $k$ conjunto absoluto de $n-1$ elementos. A continuación, vuelva a sacar el nodo superior para obtener un $k$ conjunto absoluto de $n-2$ elementos. Repite la operación hasta que te quedes con $k$ elementos. Puede hacerlo hasta que llegue a $k$ por la parte "superior" del lema superior-inferior. Esto nos da que hay equipos con $k+1, k+2, \dots, n$ gana. Ahora, haz lo mismo para los elementos menores, de nuevo usando el lema de arriba-abajo - esta vez la parte "abajo". Se acaba mostrando que hay equipos con $1, 2, \dots, k$ gana; puede detenerse en $k$ aunque $n > 2k$ porquee ya ha mostrado las victorias de $k+1$ en adelante. En conjunto, estos resultados muestran que tenemos algún equipo con $1$ ganar, otro con $2$ etc. hasta $n$ . Esto implica la unicidad por el principio de encasillamiento porque tenemos $n$ palomas (equipos) y $n$ agujeros (número de victorias) y existe un equipo para cada número de victorias.

Lemma (arriba/abajo): Demostramos que cada $k$ conjunto absoluto $U$ de $n$ equipos con $n \geq k > 2$ tiene un elemento superior y otro inferior. Lo demostramos de la siguiente manera. Sea $S$ sea el mayor subconjunto de $U$ que tiene un elemento superior. Sabemos por $k$ la absolutización de $U$ que $|S| \geq k$ . Ahora, supongamos que $S \neq U$ hacia una contradicción. Sea $t$ sea el elemento superior de $S$ . Entonces podemos elegir algunos $u \in U$ s.t. $u > t$ . Ahora, podemos demostrar que $u$ es el elemento superior de $S \cup \{u\}$ . Para demostrarlo, considere cualquier subconjunto de $S$ de tamaño $|S| - 1$ que también contiene $t$ . Llámalo $S'$ . Porque $k > 2$ cada elemento de $S$ pertenece a algún tipo de $S'$ Pero un punto crucial señalado por el comentarista Steve Kass es que este no es el caso de $k = 2$ . Ahora, por $k$ absoluto, debe haber un elemento superior de $S' \cup \{u\}$ . Bueno, porque $t$ es mayor que todos los elementos existentes que no sean $u$ Ninguno de ellos puede ser el mejor. Tampoco puede $t$ ser la parte superior ya que $u>t$ . Así que $u$ es el elemento superior. Así que, $u$ es mayor que todos los elementos de $S'$ . Como ya hemos mencionado que cada elemento de $S$ es en algunos $S'$ porque $k>2$ Sabemos entonces que $u > s$ por cada $s \in S$ . Así, el conjunto $S \cup \{u\}$ de tamaño estrictamente superior a $S$ tiene un elemento superior $u$ contradiciendo nuestra suposición de que $S$ era la parte superior. Así, $U$ debe tener un elemento superior. El mismo argumento se puede aplicar para un elemento inferior.