Las desigualdades y los cambios

Question

Algunos niños están dispuestos en dos filas, de modo que cada niño en la primera fila es más alto que el niño detrás de él en la fila de atrás. Los niños son ahora reorganizado en orden creciente en cada fila. Muestran que en el nuevo acuerdo de cada niño en la primera fila es más alto que el niño detrás de él.

Reformulación: considere dos $n$-uples de (positivo) números de $(a_1, \ldots, a_n)$ $(b_1, \ldots, b_n)$ tal que $a_i \ge b_i$ todos los $1\le i \le n$. Si $(a'_1, \ldots, a'_n)$ $(b'_1, \ldots, b'_n)$ son el aumento de la reorganización de las $(a_1, \ldots, a_n)$ $(b_1, \ldots, b_n)$ $a'_i \ge b'_i$ todos los $1\le i\le n$.

Me dijeron que la afirmación es obvia. Es? Es bastante fácil ver que $a'_1 \ge b'_1$, y también que $a'_n \ge b'_n$, pero no parece obvio para otros valores de $i$.

Answer 1

Tomar el más pequeño de los niños de la primera fila, y el más pequeño de los niños de la fila de atrás (que claramente es el más pequeño de todos los childs) tanto "fuera de concurso". Es posible reorganizar el resto de los niños de tal manera que cada niño permanece en la misma fila y otra vez, cada niño / a en la (nueva) primera fila es más alto que el niño detrás de él en la (nueva) fila de atrás? Si es así, entonces usted está hecho con la inducción. Si los dos niños mencionados fueron ya originalmente en la misma columna , a continuación, la respuesta es claramente "sí": todos los niños (excepto los dos que fueron tomadas fuera) tomar sus posiciones originales. Si no, entonces la situación es aún más favorable. El niño en la parte delantera y originalmente en la misma columna que el niño más pequeño en la parte de atrás será más alto que el más pequeño de los niños en la parte delantera por lo tanto será más alto que el niño detrás de el niño más pequeño en la parte delantera. Así que estos dos niños se colocan en una columna. Los otros niños a tomar sus lugares de origen.

Answer 2

Mire de forma inductiva. El menor hijo en la frente ($a'_1$) es claramente más alto que el más corto de niño en la espalda ($b'_1$) . Por qué? Bien, $a'_1$ era más alto que algún niño en la espalda y ese chico tenía que ser al menos tan alto como $b'_1$.

Ahora, supongamos que (inductivo) que se realiza por primera $i-1$ niños. Vistazo a la configuración original. Si $a'_1, ...a'_{i-1}$ originalmente estaban en frente de la lista $b'_1, ...b'_{i-1}$ (en cualquier orden), es evidente que el niño $a'_i$ originalmente estaba en frente de alguien no inferior a las $b'_i$. Alternativamente, se puede suponer que al menos uno de $a'_1, ...a'_{i-1}$ estaba en frente de algunos b distinto de $b'_1, ...b'_{i-1}$. Pero eso significaría que no eran más que $i-1$ de los niños en la fila de atrás más corto de $a'_{i-1}$, lo que significa que $b'_i < a'_{i-1} < a'_i$ como se desee.

Answer 3

Si ${\max\,}_l> a_l=a_j$ y ${\max\,}_l> b_l=b_j$ de la $j$ luego solo hacen el par $\left[\matrix{ a_j\cr b_j\cr}\right]$ el último par de la línea. Si ${\max\,}_l> a_l=a_j$ y ${\max\,}_l> b_l=b_k$ $j\ne k$ entonces tenemos la cadena de desigualdades $$a_j\geq a_k\geq b_k\geq b_j\ .$ $ entonces hacemos $\left[\matrix{ a_j\cr b_k\cr}\right]$ $\left[\matrix{ a_k\cr b_j\cr}\right]$ el primer par (temporal) de la línea de los último par. En ambos casos los primeros pares resultantes de $n-1$ forman una instancia admisible del problema con $n$ sustituido por $n-1$.