$m \times n$ personas se sitúan como un rectángulo de $m$ filas y $n$ columnas. Cada una es más alta que la que está a su izquierda.
Ahora, si el comandante ordena cada columna por altura, demuestre que después de dicha ordenación, cada uno sigue siendo más alto que el que está a su izquierda.
Estoy leyendo un libro de Combinatoria por mi cuenta, pero algunos ejercicios no consigo resolverlos... ¡muchas gracias!
Para una persona $a$ de pie en columna $i$ hay $k$ personas en esa misma columna que son más altas que él, y puesto que para cada persona en esta columna, hay un vecino derecho en la columna siguiente que es aún más alto, ahora que el $k + 1$ -la persona más alta de la siguiente columna es más alta que $a$ . Tras la clasificación, el vecino derecho de $a$ (el $k + 1$ -persona más alta de la columna $i$ ) es el $k + 1$ -enésima persona más alta de la columna $i + 1$ y ésta es, por tanto, más alta que $a$ .
(Al principio publiqué una salida falsa por accidente).
Que la persona en la fila $r$ y columna $c$ sea $h_{r,c}$ sea $P_{r,c}$ y que la altura de esa persona sea $h_{r,c}$ . Sea $C(r,c)=\{s:h_{s,c}\ge h_{r,c}\}$ . Supongamos que $1\le c<n$ . A continuación, para cada $s\in C(r,c)$ tenemos $h_{r,c}\le h_{s,c}<h_{s,c+1}$ . Supongamos que las columnas están ordenadas de forma que las alturas disminuyen a partir de la fila $1$ para remar $m$ . Entonces $P_{r,c}$ estará en la fila $|C(r,c)|$ y columna $c$ de la nueva formación. Si $c<n$ hay al menos $|C(r,c)|$ personas en columna $c+1$ que son más altos que $P_{r,c}$ así que la persona de la fila $|C(r,c)|$ y columna $c+1$ de la nueva formación debe ser más alta que $P_{r,c}$ .
Añadido: Ahora veo que Lieven ha publicado esencialmente el mismo argumento. Voy a dejar esto en la remota posibilidad de que alguien lo encuentra más fácil de seguir.
En realidad no es una respuesta nueva, pero sitúa la cuestión en una perspectiva algo más amplia. Tenga en cuenta que las respuestas dadas sólo tienen en cuenta un par de columnas adyacentes a la vez, el hecho de que éstas estén dentro de un rectángulo no importa realmente. También se podría permitir que las columnas fueran de diferente longitud, siempre que un lugar vacío se considere más pequeño que cualquier persona. El resultado fundamental es el siguiente.
Definir un orden parcial sobre el conjunto $A^*$ de palabras sobre un alfabeto ordenado $A$ comparando las particiones correspondientes: $(a_1a_2\dots a_n)\geq(b_1b_2\ldots,b_m)$ siempre que $n\geq m$ y $a_i\geq b_i$ para todos $i\leq m$ . Cada palabra determina un multiconjunto de letras (olvidando el orden), y cualquier multiconjunto está representado por una única palabra en la que las letras son débilmente decrecientes; esto define un mapa de "ordenación" natural $\phi: A^*\to A^*$ cuya imagen es el conjunto de palabras débilmente decrecientes. Entonces $\phi$ es un morfismo de conjuntos paritariamente ordenados: para $v,w\in A^*$ uno tiene $v\leq w\implies \phi(v)\leq\phi(w)$ . Es evidente que esto se aplica en particular a la ordenación de dos columnas adyacentes en la matriz de la pregunta. La prueba es la que se da en las otras respuestas: si la letra $k$ de $\phi(v)$ es $a$ entonces al menos $k$ cartas de $\phi(v)$ y, por tanto, de $v$ son ${}\geq a$ y así por $v\leq w$ como mínimo $k$ cartas de $w$ son ${}\geq a$ y, en particular, la letra $k$ de $\phi(w)$ es.
La afirmación dada puede reforzarse ligeramente sustituyendo ' $\leq$ por $<$ '; la prueba requiere además un argumento no tan fácil que demuestre que dos permutaciones diferentes del mismo conjunto de letras no pueden ser comparables por ' $<$ '. Una forma de proceder es comparar para un hipotético contraejemplo los conjuntos de posiciones ocupadas por la letra mayor; si estos conjuntos difieren, entonces ambas palabras tienen alguna posición en la que contienen la letra mayor y la otra palabra no, lo que contradice que sean comparables; si los conjuntos coinciden, entonces se pueden eliminar todas las letras en estas posiciones de ambas palabras y concluir utilizando la inducción sobre el valor de la letra mayor.
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.
