Partes con el número máximo de cada entero

Question

Sea $n$ un entero positivo. Algunos enteros entre $1$ y $n$ (inclusive) están escritos en una línea, donde el mismo entero puede aparecer varias veces. ¿Es cierto que siempre podemos dividir la línea en $n$ partes y asignar a cada parte una etiqueta entre $1$ y $n$ (inclusive), donde cada etiqueta se usa exactamente una vez, de manera que para cualquier $1\leq i\leq n$, la parte etiquetada como $i$ contiene al menos tantas copias del entero $i$ como cualquier otra parte?

Si $n=1$ entonces esto es trivialmente cierto, porque solo escribimos $1$s y no necesitamos dividir la línea en absoluto.

Si $n=2$ también es cierto: Ve desde la izquierda de la línea hasta que alcances al menos la mitad de todos los $1$s o la mitad de todos los $2$s, luego detente y divide la línea. Digamos que hemos alcanzado al menos la mitad de todos los $1$s. Luego etiqueta la parte izquierda con $1$ y la parte derecha con $2$.

Answer 1

Esto se sigue de la generalización de David Gale del lema de Knaster-Kuratowski-Mazurkiewicz. Consulta Wikipedia para la formulación de la generalización y la terminología relevante.

Para demostrar el teorema, primero hacemos el problema continuo:

Para cada $i=0, ..., L-1$, el intervalo (abierto) unitario $(i, i+1)$ tiene color $j$ para algún $j \in [n]$. ¿Es cierto que siempre podemos dividir el intervalo $[0, L]$ en $n$ intervalos (abiertos) disjuntos $I_1, ..., I_n$ (de izquierda a derecha) de longitud $x_1, x_2, ..., x_n$ y encontrar una permutación $\pi\in S_n$ tal que para cualquier $i\in[n]$, la longitud total del color $\pi(i)$ en el intervalo $I_i$ es al menos tanto como en cualquier otro intervalo?

Una vez que probamos la versión continua, podemos "redondear" cada intervalo de la siguiente manera. Si el punto final izquierdo $a$ del intervalo $I_i$ está coloreado con $\pi(i)$, redondeamos $a$ a $\lfloor a\rfloor$. Similarmente, si el punto final derecho $b$ del intervalo $I_{i}$ está coloreado con $\pi(i)$, redondeamos $b$ a $\lceil b\rceil. Si hay puntos finales que aún no han sido redondeados, los redondeamos arbitrariamente. Se puede demostrar que la partición resultante da una solución a la versión discreta.

Finalmente, demostramos la versión continua. Considera el simplejo $(n-1)$ $\Delta := \left\{(x_1, ..., x_n)\in \mathbb{R}^n:x_1 + x_2 + ... + x_n = L,x_1, ..., x_n \ge 0\right\}$, con vértices $v_i = Le_i$, donde $e_1, ..., e_n$ forman la base estándar de $\mathbb{R}^n$.

Para cada $x = (x_1, ..., x_n) \in \Delta$, define el intervalo (abierto) $I_i(x) = (x_1+...+x_{i-1}, x_1+...+x_{i})$ para todo $i\in [n]$, y decimos que $I_i(x)$ es dominante en el color $j$ si la longitud total del color $j$ en el intervalo $I_i(x)$ es al menos tanto como en los otros $I_*(x)$. Para cada $i \in [n]$ y $j \in [n]$, sea $$C_i^j := \{x\in\Delta: I_i(x) \text{ es dominante en el color }j\}.$$

Se puede verificar que para cada $j\in[n]$, $C_1^j, ..., C_n^j$ es una cobertura KKM. Por el resultado de David Gale, existe una permutación $\pi$ tal que $$\bigcap_{i=1}^n C_i^{\pi(i)}\neq \emptyset.$$

En otras palabras, existe $(x_1, ..., x_n)\in \Delta$ tal que $(x_1, ..., x_n)\in C_{i}^{\pi(i)}$ para todos los $i\in[n]$, es decir, $I_i(x)$ es dominante en el color $\pi(i)$.