Colección de números siempre en orden creciente o ascendente

Question

Alguien tiene alguna idea sobre esta cuestión? Creo que tienes que usar el encasillar a principio..pero no estoy seguro acerca de eso?

Los números de $1,2,3,\ldots,101$ están escritas en una fila en un cierto orden. Siempre es posible tachar $90$ números de una manera tal que todos los $11$ números de la izquierda de estancia, ya sea en aumento o disminución de la orden?

Answer 1

Este es el Erdos-Szekeres teorema sobre la monótona subsecuencias. Me estoy pegando una prueba de la wikipedia:

Dada una secuencia de longitud $(r − 1)(s − 1) + 1$, la etiqueta de cada número $n_ i$ en la secuencia con el par $(a_i,b_i)$ donde $a_i$ es la longitud de la más larga monótonamente creciente larga que termina con $n_i$ $b_i$ es la longitud de la más larga monótonamente decreciente larga que termina con $n_i$. Cada uno de los dos números en la secuencia son etiquetados con un par diferente: si $i < j $$n_i < n_j$$a_i < a_j$, y por otro lado si $n_i > n_j$$b_i < b_j$. Pero sólo hay $(r − 1)(s − 1)$ posible etiquetas en las que $a_i$ es en la mayoría de las $r − 1$ $b_i$ es en la mayoría de las $s − 1$, por lo que por el principio del palomar debe existir un valor de $i$ que $a_i$ o $b_i$ está fuera de este rango. Si $a_ i$ está fuera de rango, a continuación, $n_i$ es parte de un aumento de la secuencia de longitud de, al menos,$r$, y si $b_i$ está fuera de rango, a continuación, $n_i$ es parte de una disminución de la secuencia de longitud de, al menos,$s$.

en su problema, tome $r = s = 11$

lecturas sugeridas... algunos más exploración de monotónica subsecuencias: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i2r14

Answer 2

Asociado con cada elemento de la lista un par ordenado $(a,b)$ donde $a$ es el más largo, el aumento de larga termina en ese número y $b$ es el más largo de la disminución de larga partida con ese número. Muestran que no hay dos números tienen el mismo par asociado porque se puede ampliar la larga de los otros. Sólo hay $100$ parejas con ambas entradas $10$ o menos.