Mostrar que si hay 101 personas de diferentes alturas de pie en una línea

Question

Mostrar que si hay 101 personas de diferentes alturas de pie en una línea, es posible encontrar de 11 personas en la orden en que están de pie en la línea de alturas que se ya sea aumentando o disminuyendo.

Answer 1

Este es un caso especial de la Erdős-Szekeres teorema de con $r = s = 11$.

Aquí es una prueba para este caso especial. Estoy asumiendo que no hay dos personas tienen la misma altura. Para el $i$:ª persona $P_i$ en la línea, dejamos $x_i$ ser la longitud de la secuencia más larga de la gente detrás de $P_i$ que están aumentando en altura (incluyendo $P_i$). Dejamos $y_i$ ser la longitud de la secuencia más larga de la gente en frente de $P_i$ que están disminuyendo en altura (incluyendo $P_i$).

Ahora, para $i < j$ tenemos $(x_i,y_i) \neq (x_j,y_j)$. Esto se deduce del hecho de que si $P_i$ es más corto de $P_j$, a continuación, la secuencia más larga de aumento de alturas terminando en $P_i$ puede ser utilizado para construir una secuencia más larga que termina en $P_j$, lo $x_i < x_j$ o si $P_i$ es más alto que los $P_j$, el más largo de la secuencia de alturas decrecientes después de $P_j$ puede ser utilizado para construir una secuencia más larga de la disminución de las alturas después de $P_i$, lo $y_i > y_j$.

Por lo tanto, hemos 101 diferentes tuplas de números. Podemos colocar estos en una cuadrícula de $101 \times 101$ casilleros, y colocamos $(x_i,y_i)$ en el palomar en $(x_i,y_i)$. Cada caja se presenta en más de una tupla, ya $(x_i,y_i) \neq (x_j, y_j)$. Pero vemos que tenemos más tuplas de las que caben en un $10 \times 10$ cuadrícula de casilleros, lo que significa que al menos una tupla $x_i > 10$ o $y_i > 10$, lo que significa que hay una larga de al menos 11 personas con la disminución o el aumento de las alturas.

Answer 2

Definir un orden parcial en el conjunto de personas que, al estipular que $x\lt y$ significa que la persona $x$ es más corto de $y$ y está de pie detrás de $y$. La pregunta que nos muestran que esta parcialmente conjunto ordenado de tamaño $101$ contiene una cadena o una antichain de tamaño $11$. La forma más simple de hacer esto es observar que, en parte, un conjunto ordenado, que no contiene $11$-elemento de la cadena, es la unión de $10$ antichains, uno de los cuales debe contener más de $10$ de los elementos por el principio del palomar. El aficionado alternativa es la cita de Dilworth de la cadena de descomposición teorema: si no es $11$-elemento antichain, entonces el poset es la unión de $10$ cadenas, etc.

Answer 3

Esta es una sencilla aplicación para el principio del palomar. De hecho, una declaración más general se tiene:

Si $a_1,\ldots,a_{n^2+1}$ es una secuencia de $n^2+1$ números reales entonces se debe tener ya sea un aumento o una disminución de larga la longitud de la $n+1$.

Para una prueba de ver por ejemplo este.