Elegante prueba de combinatoria de declaración: al menos $l-k+1$ de los niños que estaban en grandes equipos

Question

Hay $n$ de los niños, que juegan a un juego donde en la ronda $1$ se derrame en $k$ equipos (cada equipo, no vacío, de a pares discontinuo). Después de un tiempo se vuelve aburrido, para formar nuevos equipos para jugar la ronda de $2$; esta vez, se dividen en $l$ equipos (cada equipo, no vacío, de a pares discontinuo), donde $l>k$, y esta será la única condición.

Demostrar que hay al menos $l-k+1$ de los niños, para los cuales su equipo en la primera ronda fue estrictamente de mayor tamaño que en la segunda ronda.

Esta fue una tarea problema en un curso el año pasado que tuve un momento muy duro de probar, y por último, un día antes de la fecha límite, he encontrado una prueba que fue de tres páginas de largo y se utiliza una desordenada de inducción con un montón de definiciones y notaciones tuve que hacer (me tomó todo el día para escribir).

Hay una elegante prueba de esta afirmación?

Si quieres ver mi prueba, el comentario de abajo y voy a tratar de resumir. Pero te garantizo que es muy complicado! :)

Answer 1

Dicen que un niño en un equipo de tamaño $m$ ocupa $1/m$ de un equipo. Decir hijo / $i$ ocupa $x_i$ de un equipo en la ronda $1$ $y_i$ de un equipo en la ronda $2$. Ahora tenemos que demostrar que hay al menos $l-k+1$ valores de $i$ que $y_i>x_i$.

Pero $\sum_ix_i=k$$\sum_iy_i=l$, lo $\sum_i(y_i-x_i)=l-k$. Cada término de esta suma es estrictamente menor que $1$, por lo que debe ser estrictamente mayor que $l-k$ términos positivos.

Answer 2

Vamos a no ser $n$ niños. Supone que hay al menos 1 niño que está en un pequeño o igual que el tamaño de grupo en la ronda 1, que en la ronda 2. Vamos a examinar lo que sucede con este niño sea retirado.

Caso 1: El niño en la ronda 1 y la ronda 2 del grupo sigue siendo no-vacío. Esto se traduce en $n-1$ de los niños, pero no cambio $k$ o $l$.

Caso 2: El hijo de la ronda 1 se convierte en vacío. Esto se traduce en $n-1$ de niños $k-1$ grupos en la ronda 1 y $l$ grupos en la ronda 2. Entonces la pregunta es para probar que hay, al menos, $l - (k-1) + 1 > l - k + 1$ a los niños para que su equipo en la primera ronda fue estrictamente de mayor tamaño que en la segunda ronda.

Caso 3: El niño en la ronda 1 y la ronda 2 se vacía. Esto se traduce en $n$, $k$, $l$ todos reducido por 1 y no cambia la cuestión.

Caso 4: El hijo de la ronda 2 se convierte en vacío. Esto es imposible, ya que significa que la ronda 2 del grupo tiene un tamaño más pequeño.

Con la por encima de los 4 casos, podemos concluir que si queremos eliminar todos los niños que es de menor o igual tamaño de grupo en la ronda 1, que en la ronda 2 y termina con $n'$ de niños $k'$ grupos en la ronda 1 y $l'$ grupos en la ronda 2, la cantidad resultante $l' - k' + 1 \ge l - k + 1$.

Todo hay que hacer es mirar a $n'$ de los niños con todos los niños en ronda 1 en un grupo más grande que en la ronda 2. Dejar a estos niños en grupos de a $K_1,...,K_{k'}$ en la ronda 1 y $L_1,...,L_{l'}$ en la ronda 2 (no vacío, de a pares discontinuo). Es claro que hay al menos $l' \ge l' - k' + 1 \ge l-k+1$ niños.